- *** Binary Tree Traversal.
Depth First Traversals: Code GFG
Time Complexity: O(n) where n is number of nodes in the binary tree
Inorder: Left, Root, Right
– [Pending] Morris Traversal for Inorder ( No stack, No Recursion) (Code, GFG)
– Iterative using Single Stack without recursion ( Code, GFG)
PreOrder: Root, Left, Right –
– Iterative Code (implemented using Stack without recursion) GFG
– Morris Traversal for PreOrder(Code, GFG)
PostOrder: Left, Right, Root
– Iterative Postorder Traversal( using two stack, no recursion, GFG. Code)
– [Skip] Iterative Postorder Traversal( using one stack, no recursion, GFG. Code)
Breadth First or Level Order Traversal – Code GFG
Time Complexity: O(n) where n is number of nodes in the binary tree
Is there any difference in terms of Time Complexity?
All four traversals require O(n) time as they visit every node exactly once.
Is there any difference in terms of Extra Space?
There is difference in terms of extra space required.
– Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.
– Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.
How to Pick One?
- Extra Space can be one factor (Explained above)
- Depth First Traversals are typically recursive and recursive code requires function call overheads.
- The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.
- *** Print level order traversal line by line. Code. GFG
Algo: We change the original level order queue implementation. Now we need to count the nodes at current level.And for every node, we enqueue its children to queue. Check code.
Asked in: Amazon, Microsoft, Morgan-Stanley
*** Binary Tree – Inorder Traversal – Using Stack (no recursion) Code. GFG
Algo: Inorder:Left, Root, Right. We keep pushing the left node to stack(We don’t push the right node onto the stack initially.). Then start poping from stack. Since we have the left node, we can print that value.
But we also need to handle the case that the node has a right node. So now we check if the current node that was poped has a right node. If yes, then we push this right node and all corresponding left node to the stack. In the next iteration these nodes will be poped first( stack is FIFO).
- *** Size of Binary Tree – number of nodes in the tree. Code. GFG
Algo: We need to do this recursively.
Size of a tree = Size of left subtree + 1 + Size of right subtree.
- *** Maximum Height/Depth of a Binary Tree –
Note: This is different from size of the BT
Iterative: GFG – This logic is based on traversing the node level wise. For each level traversed we increment the tree height by 1.
Recursive: Code, GFG This code is similar to finding the size of BT. Here we calculate the size of left and rigth tree and return the maximum of these.
Asked in: Amazon, Cadence, CouponDunia, FactSet, FreeCharge, Monotype, Snapdeal, Synopsys, Teradata, VMWare
Delete a Binary Tree – GFG
Algo: Delete each node of tree recursively. Start at the leave node. Set the leave node to null and keep doing the same till the root node. Next set the root to null as well.
- *** Convert a Binary Tree into its Mirror Tree – GFG
Algo: Start at the leave node. Swap the left and right node. Move upwards in the same manner.
- If you are given two traversal sequences, can you construct the binary tree?
If one of the traversal methods is Inorder then the tree can be constructed, otherwise not. GFG
Therefore, following combination can uniquely identify a tree.
Inorder and Preorder,
Inorder and Postorder
Inorder and Level-order.
And following do not – Postorder and Preorder, Preorder and Level-order, Postorder and Level-order
- *** Print all Root to Leaf paths of a Binary Tree. GFG Code.
Algo: The thing to note here is how the array is being passed around in recursion. We can use the Array or ArrayList in recursion.
Similar: Print any node to leaf path in a binary tree. Code
- Count of leave nodes in binary tree. Code GFG
Algo: This is also very similar to counting the size of a binary tree. We just need to changed the condition.
- **** Level order traversal in spiral form. Code. GFG
Algo: The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes, and push nodes of next level in other stack.
- ** Check for Children Sum Property in a Binary Tree Given a binary tree. Write a function that returns true if the tree satisfies below property. Code GFG
Algo: If we follow an in-order approach, the problem boil down to first verifying that the last node is balanced and then move up the tree from leaves and verifying each tree. For the return value, we use a boolean. If the sum property is satisfied we return boolean. We don’t return the current tree sum. The tree that is calling left and right will verify before calling it’s children that the sum property is valid.
Following the same logic, with pre-order traversal simplifies the problem, as we first validate then move down the tree, instead of going to the leaf node and then moving upwards.
- [Pending] Convert an arbitrary Binary Tree to a tree that holds Children Sum Property. GFG. Check code on GFG.
Algo: Do a post oder traversal. Find the sum of the child node.
– If the sum of child nodes adds up-to the node then no changes are required.
– If the child nodes sum is greater then the node, then add the diff to the node data directly as it won’t dis-balance the rest of the tree’s sum property.
– If node’s data is greater than the node’s children sum, then increment one child’s data. In doing that we disturb the already balanced sum property below that node. To balance that we can choose to increment either left or right child if they both are not NULL. Let us always first increment the left child. Incrementing a child changes the subtree’s children sum property so we need to change left subtree also. So we recursively increment the left child. If left child is empty then we recursively call increment() for right child.
- [Pending] *** Diameter of a Binary Tree. Article GFG. Debug Code
Algo: The diameter of a tree is the longest distance between two nodes. It can either pass through the root or not. So we need to check this for every node.
We recursively check both nodes – left and right diameter and the left and right height. Then we calculate the max of these are return to the calling node. This continues till the root node.
- **** Root to leaf path sum equal to a given number – Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number. Return false if no such path can be found.
Code. GFG Asked in: Accolite, Adobe, Amazon, CouponDunia, Housing.com, Microsoft, Oracle, Samsung
1. Here we follow the logic to print nodes at each level wise. We can maintain an array/arraylist of all nodes data till a given point. And then at the leave node we find all these sum to compare with the given sum.
The approach takes extra space to save and pass the array. The approach can be used when we need to also print the path with the given sum. This can be used to print the sum of all the path from root to leaf node.
2. Time Complexity: O(n)
We are given a sum initially in the problem statement. At each node keep decreasing that sum by the node value. Then for each node we check if the sum has reached and it’s a leaf node. If yes we can return a boolean. So this approach has the benefit that we don’t have to pass the current sum and we can just work with a boolean return type.
- **** Construct Tree from given Inorder and Preorder traversals.
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
*** Similar: Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root. GFG
Time Complexity: O(n^2)
Algo: Uses the same logic to create a new tree. The maximum element in given array must be root. The elements on left side of the maximum element are in left subtree and elements on right side are in right subtree.
*** Similar: Construct a special tree from given preorder traversal. GFG.
- Create a Double tree. GFG
Algo: We can either start from the leaf node or from the root.
1. Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child. Same code as on GFG.
2. Recursively convert the tree to double tree in postorder fashion. create a duplicate node of the node and fix the left child of the node and left child of left child. Then call the left and right node recursively. Code
- Width of a binary tree. Code 1 GFG
1. We can use the level order travesal logic using queue to find the max width and print the width of each level. Code 1
2. We can also use pre-order traversal logic here. In this method we create a temporary array count of size equal to the height of tree. We initialize all values in count as 0(or use an arraylist simply). We traverse the tree using preorder traversal and fill the entries in count so that the count array contains count of nodes at each level in Binary Tree. At the end determine the level with maximum value.
- Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root. GFG
1. We can do a preorder traversal and keep passing around the value of level in the recursive method. When we reach the required level we print and return. Code on GFG is pretty simple.
2. We can use level order traversal with queue and keep counter the level. When we reach the required level empty the queue and break
- Given a Binary Tree and a key, write a function that returns level of the key.
Algo: Same logic as the above question(20 or on GFG)
1. We can do a preorder traversal and keep passing around the value of level and the key in the recursive method. When we find the required key, we print the level value and return.
2. We can use level order traversal with queue and keep counter the level. We eed to check if the required key is there before pushing to queue.
- ***** Print Ancestors of a given node in Binary Tree. GFG
1. We can create all possible path and keep storing them in an array and passing it around. This is the same logic here – Print all Root to Leaf paths of a Binary Tree.(Q 10 on this page) GFG iDeserve Code. But this requires extra space.
2. *** We need to call both the left and right tree recursively. If the node exists in the tree then, we will reach that node at some point of recursion and after that we will keep printing all the previous calling node(which will basically be the node from leaf to root).Code
Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.
- **** Check if a given Binary Tree is SumTree. GFG
Algo: The algo given in GFG has bad complexity or the logic is complex. We can easily do it in O(n) using post order traversal. A similar C solution is posted by a user (mr. lazy). This is exactly same solution we personally came up with. Now the case to handle here is when there’s a mismatch(last line of recursive method). In that case we pass the maximum possible negative/positive number using Integer.MAX_VALUE. Code
This question is different from this.
- **** Check if a binary tree is subtree of another binary tree.
Asked in: Cavisson System, Microsoft
1. GFG. Check at each node if both nodes are same. O(n^2). Code
We can also find the root to the sub-tree in the tree. Now that we have both the root we can simply write a method to check if both of these are same. This is also O(n^2)
2. GFG The idea is based on the fact that inorder and preorder/postorder uniquely identify a binary tree. Tree S is a subtree of T if both inorder and preorder traversals of S are substrings of inorder and preorder traversals of T respectively.
1) Find inorder and preorder traversals of T, store them in two auxiliary arrays inT and preT.
2) Find inorder and preorder traversals of S, store them in two auxiliary arrays inS and preS.
3) If inS is a subarray of inT and preS is a subarray preT, then S is a subtree of T. Else not.
- *** Connect nodes at same level – with and without extra space
1. It’s same as level order traversal for printing each level on a new line.
Use queue and level order traversal. Update the queue’s value being polled to the top of the queue address. O(n) but no constant space.
- Finding a node in a Binary Tree. Code