BRANCH SUMS


     Write a function that takes root of binary tree as a input and returns sum of its nodes depths.

Approach -  Create a variable depth_sum and depth, depth will store current depth of binary tree and d_sum will store the total sum of depths.


 O(n) time, O(h) space[h is the height of binary tree]

node depths solution


 Please leave comment for any suggestions or topic you would like to read.


 

Comments

Post a Comment

If you have any doubt, Please let me know

Popular posts from this blog

MINIMUM HEIGHT BST

Image
  Given a non-empty sorted array of distinct integers, construct a minimum height bst and return       root . Approach : Since the array is element at the middle of array is going to be the root. So we will try break the array in 3 parts( left array, middle element, right array). Middle element will be the root of the array, then we will find the middle of left array it will be the root of left sub tree and similarly the middle of right array will be the root of right sub tree.          We defined tree as None since there is no node in the tree. Now we will be inserting nodes in the tree using minHeightBstHelper function.                BST is a class which inserts the node at its right place following the bst properties. Time - O(n log n)   Space - O(n)  Solution -  min height bst solution Can you reduce its time complexity of O(n), do post the solution in comment. P...
Read more

CHECK IF GIVEN BINARY TREE IS A BST/ VALIDATE BST

Image
 Question link :  validate bst practise Approach -      Take variable maxRange assign it as big positive number, minRange assign it as big negative number.  When we move to left sub tree then our maxRange will be tree.value as per the properties of bst.  Similarly as we move towards right sub tree our min range will be tree.value.  If at any point property of bst fails we will return false.  If both left sub tree and right sub tree follows the property then we it means that given binary tree is a   bst.  time - O(n) : as we need to move to all nodes in a tree. space - O(d) : Auxillary stack space needed by recursion where d is the depth of tree.  Solution -  validate bst solution Please leave comment for any suggestions or topic you would like to read.
Read more

Kth LARGEST ELEMENT IN BST

Image
  Find the Kth largest element in bst. Approach 1: Use inorder traversal to store the tree elements in an array. The array will be in sorted order.     Element at index (n - k) will be answer. Where n is the length of the array. time - O(n) space - O(n) Solution -  kth largest element using inorder   Approach 2 : Reverse Inorder Technique We will create a class node which stores value(we will store the tree node values there ), counter(ctr), it store the count of variable. Now we will create nde of class node that keep track of value and kth index and pass it to the helper function. 3. We will traverse right of bst and then to left. And we will check the condition if we are at the kth node. Also we will store the value of node we visit. Time - O(h + k) space - O(h) where h is the height of the tree Solution -  kth largest element using reverse inorder Please leave comment for any suggestions or topic you would like to read.
Read more