Binary Tree – Set 2

BT Set – 1, BT Set – 3 , Question Set(41-101)
Binary Tree Visualizer

  1. *** Populate Inorder Successor for all nodes GFG Code
    Algo:
    1. Traverse the given tree in reverse inorder traversal and keep track of previously visited node. When a node is being visited, assign previously visited node as next.
    Time Complexity: O(n)
    2. This is also referred to as Threaded Binary Tree. GFG
    The same can be easily implemented using queue.We first do an inorder traversal of the tree and store it in a queue (we can use a simple array also) so that the inorder successor becomes the next node. We again do an inorder traversal and whenever we find a node whose right is NULL, we take the front item from queue and make it the right of current node. We also set isThreaded to true to indicate that the right pointer is a threaded link. See This GFG solution is unnecessarily complicated. Code


  2. Convert a given tree to its Sum Tree – Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0. GFG Code

  3. Vertical Sum in a given Binary Tree – Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
    GFG Code
    Algo: We need to check the Horizontal Distances from root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
    We can do inorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1.
    We use hashmap because as hd will be negative and so array can’t be used(no negative array index).


  4. *** Print a Binary Tree in Vertical Order. Code GFG
    Algo: The basic concept is same as the above question. GFG has over complicated the solution in this case. We only need to traverse the tree once and store all the nodes at each horizontal distance is a map. Then print the map. Since we want the horizontal distance to displayed in order we will need to use TreeMap.


  5. ** Given a Binary Tree, find the maximum sum path from a leaf to root. GFG Code
    Algo:
    We use the logic for printing the nodes from root to leave node. Since in that we save the entire path for all possible route that will use a lot of space. We  modify that code to pass the maximum sum as int instead of passing array/arraylist (this will be done instead of printing the array) . Also we would need to store the  node where we found the max value.
    Since it the above case we used to print the entire array, but here we are not storing that. So we will have to write a method to print all nodes from target node. This can be seen in the code link here.


  6. *** Check whether a binary tree is complete or not. Article. Code. GFG 
    Algo:
    – A binary tree is a complete binary tree if all levels of the tree starting from root node level are filled.
    – Only the last level of the tree is allowed to have an incompletely filled state.
    – Also for tree to be a complete binary tree, all nodes should be placed as left as possible.


  7. Check whether a binary tree is a full binary tree or not – A full binary tree is defined as a binary tree in which every node other then the leave node has two children (SO). Conversely, there is no node in a full binary tree, which has one child node. GFG
    Algo: A full binary tree is a tree in which every node other than the leaves has two children. So just check for this condition. Except the root node, all other nodes will have two children.
    If left is null and right is not null or vice-verse for non-leaf node it’s not a full binary tree.


  8. **** Boundary Traversal if binary tree. GFG. Code . Article
    Algo:
    We need to print the left boundary, right boundary and other nodes separately. All can’t be handled in a single loop. See the code comments for pitfalls.



  9. Reverse Level Order Traversal. GFG Code is simple and same as in GFG.
    Algo: Use queue and stack. We can easily modify the  queue logic of level order traversal. Instead of poping a value we add it to a stack. So the first element that was originally printed is pushed to bottom to stack and the last element is at the top of stack.
    Since we need to print the level in order left to right, we shd push the value accordingly. So we push the right node before left node, this way left node is poped before right node and the level order is also maintained.


  10. *** Convert a given Binary Tree to Doubly Linked List. Code GFG
    Algo: We need to maintain a head that points to the first element in the inorder traversal. And we need to maintain a prev node which is used to set the prev of the DDL.
    If we do a inorder recursive traversal then first time both left and right are called is in the left most leaf node(here). So here we find our head DLL. Now we need to maintain the prev node so that we can connect the left of next node(which is prev in DLL) in the inorder traversal to it.


  11. ** Construct Complete Binary Tree from its Linked List Representation – GFG Read full question details on GFG.
    Algo: The idea is to do Level order traversal of the partially built Binary Tree using queue and traverse the linked list at the same time.
     We will use queue for this.
    So to start we create a node with the data from the head of LL to the queue. Then we start traversing the linked list until it’s empty. We take two item(if they exists) from the LL and create two tree Node. Then dequeue the Node from  queue and add these newly created Nodes as it’s left and right child. Now add these right and left child to end of queue.


  12. *** Difference between sums of odd level and even level nodes of a Binary Tree. GFG. Asked in Amazon
    The solution given on GFG is awesome, but personally that not easy to come up in an interview.
    Algo: 
    1. Use level order traversal. We keep track of the level and update the sum accordingly for each node level wise.
    2. We can do it recursively using preorder traversal. At each recursive call we pass the current sum and the level. We update the result accordingly. C++ Code


  13. Construct a Binary Tree from Postorder and Inorder. GFG
    Algo: Same logic as to construct a tree from preorder and inorder (GFG). The only diff is the in preorder the root will be at the end. So we first find the root element from the end and then find that element’s position in inorder and split inorder based on that index.


  14. Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.
    GFG
    Algo: This approach is completely based on the logic to construct a tree using inorder and preorder traversal are given. Instead of creating we just print these. The logic is same. Code .
    The printing things works because first the left most node is formed and then the right most node and so on…and postorder is left, right and root….


  15. Find depth of the deepest odd level leaf node. GFG
    Algo: We can do it simply using recursion. Just keep passing the level and return the max level. We can also do it via level order traversal


  16. Given a Binary Tree, check if all leaves are at same level or not. GFG
    Algo: The idea is to first find level of the leftmost leaf and store it in a variable leafLevel. Then compare level of all other leaves with leafLevel, if same, return true, else return false. We traverse the given Binary Tree in Preorder fashion. We need to keep a check if the variable which stores the leftmost node level is set of not. If it’s not set, then set it when we encounter the first leave node. After that whenever we find a leave node, we compare the node level with the leftmost node level and return true and false. The entire call is made recursive and when a false it returned the recursion stops.


  17. Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. GFG
    Algo:
    1. We can use level order traversal and print the first node in every level.
    2. We can  do this using preorder traversal. We need to print only one node per level. So we need to keep track that the level that has been printed yet or not.
    We can do this using a hashset or we can use a single variable in this case. We create a variable which indicates the maximum level that has been printed till now. So if the level is greater than the maximum level that has been printed don’t print that level else print the level and update the maximum.


  18. Extract Leaves of a Binary Tree in a Doubly Linked List. GFG Code
    Same as Q10 on this page (GFG)
    Algo: We need to traverse all leaves and connect them by changing their left and right pointers. We also need to remove them from Binary Tree by changing left or right pointers in parent nodes.  In the following implementation, we add leaves at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order.
    Look at the code, we should avoid using class variables.
    Time Complexity: O(n)


  19. Deepest left leaf node in a binary tree. GFG
    Algo: We need to keep track of the node at the deepest level. So we need a node to hold the deepest node found till now and the level. We also need to keep track of deepest node encountered till now and whether the node is left or right node. So in all 3 – result node, max level node and current level.  We can pass level as pass by value. But we need to keep track of result(deepest node till now) and  deepest level. We can do either make two static variable or class instant or make new class. Check the GFG code for level class logic, which comes handy in many question using recursion.


  20. Find next right node of a given keyGFG
    Algo:
    1. Level Order Traversal. The solution on GFG has been complicated(don’t know why). We do a Level order traversal and when we find the given key, we just check if the next node in level order traversal is of same level, if yes, we return the next node, otherwise return NULL.
    2. Preorder traversal. Here we only need to include the key on the same level else it won’t work.  When we find the key we get it’s level. Then we move right and print the node on the same level.


  21. Sum of all the numbers that are formed from root to leaf paths. GFG
    Algo: The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.


  22. ***** Lowest Common Ancestor in a Binary Tree – Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor.  GFG Code
    Algo: We need to do a preorder traversal and keep track of which subtree return that both n1 and n2 are found. (In the code I wrote I was passing boolean to keep track but we will have to pass the node as we need to print the node data finally).
    The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
    We need to handle the case that both are present in the tree as well.


  23. **** Given two nodes in a binary tree, find the dis­tance between them. GFG. Article Code
    Algo:
    Distance(X, Y) = Distance(root, X) +Distance(root, Y) — 2*(Distance(root to LCA(X,Y)


  24. ****  Given a binary tree, find the distance of given node from the root. Code
    Note: Distance is the number of edges b/w given node and the root. Should clarify it in an interview as some consider the nodes b/w given node and root(both included). 


  25. Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. GFG
    Algo: This is a problem that uses similar logic to printing all ancestor of a leave node( Q10 in set1 GFG  Code or q22 set 1 Code).
    The first one stores the entire path for each path and prints it when it hits a leave node. The other is a recursive method to find and print all nodes, sweet and simple.
    Here we  can use can use the first approach easily. Just build up the array path from root to leave and when we find a leave root, and print the element at n – k -1 position where n is the total element in the path and -1 because we need to exclude the leave element as it also included in that array generated. We will have to keep track what node has already been printed. We can either have an array or use a hashset if all node elements are unique.


  26. [Pending] Print all nodes at distance k from a given node.  GFG

  27. *** Construct a binary tree from given Inorder and Level Order Traversal
    GFG – 
    We can stick to GFG solution
    Algo: The first element in the level order will be root. We search for this root element in inorder. This divides inorder into two part – left and right. Now we need to search for the first element in level order in the left and right part of the sub-array created above. O(n^3) – worst case.


  28. Find the maximum sum leaf to root path in a Binary Tree. GFG

  29. Reverse alternate levels of a perfect binary tree. GFG
    Algo:
    – Do an inorder traversal and store all the odd level node data in an array. Then reverse the array. Again do a inorder and replace the value at each odd level node with the value in the array(you will have to maintain a pointer in that array as to which value has to be replaced next).
    – We can also do a level order traversal. So all the odd level node in an array and then reverse the node value.
    Better Solution   O(1) space complexity and O(n) time complexity.


  30. Given the binary Tree and the two nodes say ‘a’ and ‘b’, determine whether the two nodes are cousins of each other or not. GFG
    Two nodes are cousins of each other if they are at same level and have different parents.
    Algo: The idea is to find level of one of the nodes. Using the found level, check if ‘a’ and ‘b’ are at this level. If ‘a’ and ‘b’ are at given level, then finally check if they are not children of same parent. Find the level of both nodes given. While finding the level also find the parent of both the nodes.


  31. ***** Serialize and Deserialize a Binary Tree – GFG, Article, Code
    Algo:
    We can store the preorder of a binary tree and then regenerate the entire tree from this( This is possible only if we mark the leave node as well in the preorder. So when we store preorder we store the leave node node as null. This helps us to regenerate the tree just using the preorder which is otherwise not possible)
    –  If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.
    – For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.
    –  A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.
    – A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree. A simple way to optimize it by just storing the preorder traversal with the value for all null nodes marked.
    So this will require storing n+1 marker for n keys. This can be further optimized by using only a single bit to mark the internal and external node and single bit to mark null.
    Similar: Succinct Encoding of Binary Tree GFG
    Same logic as above.


  32. Given a binary tree and two level numbers ‘low’ and ‘high’, print nodes from level low to level high. GFG
    Algo:
    Simple level order traversal


  33. [Pending] *** Given a Binary Tree and a key ‘k’, find distance of the closest leaf from ‘k’. GFG
    Algo: 

    The main point to note here is that a closest key can either be a descendent of given key or can be reached through one of the ancestors.
    The idea is to traverse the given tree in preorder and keep track of ancestors in an array. When we reach the given key, we evaluate distance of the closest leaf in subtree rooted with given key. We also traverse all ancestors one by one and find distance of the closest leaf in the subtree rooted with ancestor. We compare all distances and return minimum.


  34. Print Nodes in Top View of Binary Tree  Optimization
    Algo: We need to print the nodes on the basis of horizontal level. If the node on that particular level has not been yet printed then it is a part of top view(as when viewed from top, only one node at the top of a hd will be visible). So we can do a level order traversal to print the nodes in order or use preorder traversal. To keep track if a node has been already printed we can use a hashset. Other way to achieve this is to maintain two pointers, left  and right. At any particular level we print only if the given hd for a node is smaller then the left or greater than right. Update left and right accordingly.
    Same logic used here – Print a Binary Tree in Vertical Order


  35. ** Bottom View of a Binary TreeGFG
    Algo: We will have to do a level order traversal here. I couldn’t come up with a recursion solution.  The following are steps to print Bottom View of Binary Tree.
    1. We put tree nodes in a queue for the level order traversal.
    2. Start with the horizontal distance(hd) 0 of the root node, keep on adding left child to queue along with the horizontal distance as hd-1 and right child as hd+1.
    3. Also, use a TreeMap which stores key value pair sorted on key.
    4. Every time, we encounter a new horizontal distance or an existing horizontal distance put the node data for the horizontal distance as key. For the first time it will add to the map, next time it will replace the value. This will make sure that the bottom most element for that horizontal distance is present in the map and if you see the tree from beneath that you will see that element.
    (every node also has a hd value in the Node structure. In recursion we could easily pass the hd but here we are updating the node value similarly. Instead of passing the node value we save it in the node and use it when it’s popped from queue).


  36. *** Perfect Binary Tree Specific Level Order Traversal. GFG
    Variation asked in Amazon
    Algo: Need to recognize the pattern and then it’s simple level order traversal.
    The standard level order traversal idea will slightly change here. Instead of processing ONE node at a time, we will process TWO nodes at a time. And while pushing children into queue, the enqueue order will be: 1st node’s left child, 2nd node’s right child, 1st node’s right child and 2nd node’s left child


  37. Convert left-right representation of a binary tree to down-right. GFG. Article
    Algo: The idea is to traverse the tree in postorder fashion and for every node
    – If its left child is empty, then make its right child as left and set right to null.
    – If left child already exists, then make right child of its left child to point to its right child and set right child to null.



  38. [Pending] Minimum no. of iterations to pass information to all nodes in the tree. GFG Asked in Amazon

  39. Given a binary tree,remove all the half nodes – Code GFG
    Algo: The idea is to use post-order traversal to solve this problem efficiently. We first process the left children, then right children, and finally the node itself. So we form the new tree bottom up, starting from the leaves towards the root.


  40. *** Clone a Binary Tree with Random Pointers – This is similar to cloning a linked list with random pointer(GFG). The same hash logic can be applied here. GFG

  41. Find sum of all left leave in a binary tree. GFG
Advertisements

2 thoughts on “Binary Tree – Set 2

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s