Last minute interview questions - Fast prepare

      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.  

  Write a function that takes in a Binary Tree and returns a list of its branch sums ordered from leftmost branch sum to rightmost branch sum. A branch sum is the sum of all values in a Binary Tree branch. A Binary Tree branch is a path of nodes in a tree that starts at the root node and ends at any leaf node. Each BinaryTree node has an integer value, a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null. OUTPUT -     [15, 16, 18, 10, 11] // 15 == 1 + 2 + 4 + 8 // 16 == 1 + 2 + 4 + 9 // 18 == 1 + 2 + 5 + 10 // 10 == 1 + 3 + 6 // 11 == 1 + 3 + 7 APPROACH - Take a variable currentSum = 0 and array = [], now traverse the tree using dfs and when you are on root node just append currentSum to array and return, remember when ever you are on any node just add the value of that node to the currentSum. time : O(n),  space : O(n) branch sums solution   Please leave comment for any suggestions or topic you ...

 An array of integer makes a bst obtained by inserting values from left to right in bst. Write a function that takes 2 arrays and determines whether they are same bst or not.  NOTE : CONSTRUCTING BST IS NOT ALLOWED. SAMPLE TEST CASE 1:  arrayOne :  [10, 15, 8, 12, 94, 81, 5, 2, 11] arrayTwo :  [10, 8, 5, 15, 2, 12, 11, 94, 81] SAMPLE OUTPUT :   true            Approach :   We know that we have to traverse array from left to right, so its obvious that element at 0th index will be the root of the tree. So we will break the problem into smaller problem first we will check if 0th element of both the array is same then it can be same tree. Now we will break array 1 into two array i.e. leftOne(array that will make left sub tree), rightOne(array that will make right sub tree. For arrayOne : leftOne = [ 8, 5, 2] , rightOne = [15, 12, 94, 81, 11]           getSmaller returns leftOne and ...

  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.

  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...

 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.

 Ways to traverse in a bst. 1. Preorder Traversal  -           Use root left right technique, i.e. first visit root then visit left sub tree and then visit right subtree.          First time it may look confusing but its fairly simple a look on code snippet below.          Root is the starting node and array holds the preorder of the array. 2. Inorder Traversal          Use left root right technique, i.e. first visit left sub tree then visit root and then visit right subtree. 3.  Postorder Traversal             Use left right root technique, i.e. first visit left sub tree then visit right subtree and  then visit root . time - O(n) : because we will be visiting all the nodes in the tree. space - O(n) : space required by array to store the order of bst.   Code link -  traversal in bst Please leave comment for any sug...

 Purpose is to find the nearest value to the target node in the binary search tree. Approach    We will define a INT_MAX variable which will store the difference between target and current node value.  We will try to minimize the difference, and the node with which we will get the minimum difference   will be the answer. We will store minimum value(which is currently INT_MAX) and answer node in array named curr. i.e. curr[0] contains minimum value         curr[1] contains answer(nearest node) code link -  closest value in bst Please leave comment for any suggestions or topic you would like to read.