Unfold Binary Tree Family Problems - Part 1/2
Chapter 3: A Deeper Look Into Depth-First Search Approach.
Table of Contents
Introduction
Black magic turned his life upside down.
1. Traversal Problems
1.1 Inorder Traversal.
1.2 Preorder Traversal.
1.3 Postorder Traversal.
1.5 Binary Tree Paths.
2. Boolean Problems
2.1 Validate Binary Tree.
2.2 Same Binary Tree.
2.4 Balanced Binary Tree.
3. Family Patterns
4. Recap
5 Next Post
Introduction
7PM is the time for his daily walk. He was happy with this walk because it was an opportunity to try the new running outfit that his wife brought to him. As usual, he started walking from the 7-Eleven store around the corner. This time, he was heading to the west. his stop point was High Park, which is where he used to spend his weekends. he was over the moon listening to this new song by his favorite singer The Weeknd on Spotify while enjoying the walk.
Suddenly, the air turned black all around him. A man wearing all black loomed out of this darkness. he started to get closer carefully…, then It was him! The Lord Voldemort! In a blink of an eye, he recited some words cursing him with his black magic, then disappeared. he was terrified by what has happened. he quickly got back home running. he checked his body, but everything with him seemed okay, and nothing had changed.
Four hundred years later, one of his descendants, Harry, noticed something strange. Everyone in the family had only two children at most. So, he started to investigate by drawing the family tree, and it looked like this:
After tracing back and conducting extensive research on the family history, he found the reason. It was him, Voldemort’s black magic!
Harry has found out that this type of black magic is called Binary Tree, so he continued studying it. He discovered that he could count all his family members by this simple equation:
Where h = the height of the binary tree (full binary tree).
⚑ Note: Binary Tree Height
The height of a binary tree is the largest number of edges, starting from the root note (great ancestor) to the most distant leaf node.
So, Harry tried to use the formula above to calculate his family numbers as follows, when h =3:
Also, he discovered that he could convert any binary tree to an array. A representation that can help him to find the children indices of any parent x if he knows the parent index i:
He tried to use the formula to confirm the location of himself and his sister in the family tree:
Today, we will discuss one of the most influential families in this series! There is no interviewer who will not think of bringing up a question from this family. The reason for that is because of its richness of important algorithm techniques, which we will encounter frequently in future posts.
The post is divided into two parts: part 1 focuses on different ways to traverse a binary tree, while part 2 focuses on some problems that require you to validate the existence of a specific pattern in a binary tree:
1. Traversal Problems
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Binary Tree Paths
2. Boolean Problems
Validate Binary Tree
Same Binary Tree
Symmetric Binary Tree
Balanced Binary Tree
So, let us get started!
1. Traversal Problems
We will start the binary tree family with the Traversal problems branch. Traversal problems represent one of the main building blocks of any binary tree problem because you can not do any operation on the tree if you do not know how to traverse it, and that is why in this section, we will talk about four different ways to traverse any binary tree.
1.1 Inorder Traversal
An inorder traversal is an approach to visiting all the nodes in a binary tree in the following order :
That means we need to visit the left child, then visit the parent node, and finally, visit the right child. This behavior will also be generalized across the subtrees. We visit the left subtree, then the parent of those subtrees, then the right subtree.
1.1.1 Problem Description
In this problem:
We are given the root of a binary tree, root, and we want to traverse the tree in an inorder traversal approach.
1.1.2 Example
Input:
Output: [7, 8, 6, 10, 5, 7, 4]
1.1.3 Solution
Let us take a single-parent binary tree with two leaf nodes, as follows:
If we have a list result, to collect the nodes' values, we can imagine our solution will look like this:
result.append(8)
result.append(10)
result.append(7)Now, what if our tree becomes bigger like this:
We can notice something here: the left child and the right child become parent nodes to other leaf nodes. And this pattern will continue as the binary tree becomes bigger. Thus, that means we deal with a repetitive pattern, which will remind us of a popular algorithm technique, recursion.
Recursion means a function that calls itself. Here we are interested in repeating the above code and generalizing it from a binary tree of a single parent to a binary tree of multiple parents. Then our above code will look like this:
def f(root):
# ......
f(root.left)
result.append(root.val)
f(root.right)
# ......Instead of storing the left and right children directly, we pass them to a recursive function f where the append operation happens for the root (parent) node. This will isolate us from thinking about the whole tree and let us keep focusing on a single node. In other words, we will let that worry of visiting all the subtrees to the recursive function f.
Our main example will be processed by the above code snippet as follows:
Now, let us see the complete code below:
def inorderTraversal(root):
def traversal(root, bag):
if root:
traversal(root.left, bag) # left subtree.
bag.append(root.val) # parent.
traversal(root.right, bag) # right subtree.
return bag
if root is None:
return []
else:
result = []
traversal(root, result)
return resultAnd, here is a clean version of the code:
def BT_inorder_traversal(root):
def traversal(root, bag):
if root is None: # is it an empty node?
return []
if not root.left and not root.right: # is it a leaf node?
return bag.append(root.val)
if not root.left: # is it a parent node with a single right child?
bag.append(root.val)
return traversal(root.right, bag)
if not root.right: # is it a parent node with a single left child?
traversal(root.left, bag)
return bag.append(root.val)
traversal(root.left, bag)
bag.append(root.val)
traversal(root.right, bag)
result = []
traversal(root, result)
return resultTime Complexity:
We can notice that every node is visited just once, so the time complexity will be:
Space Complexity:
The space complexity for a binary tree is:
Where h = the height of the tree. So, it is measured by the longest path from the root node to a single leaf node. The space complexity will consist of the stack memory size ( an implicit memory that is allocated for recursive function calls) plus the size of the result list (which will store the nodes’ values). Then, that will result in the space complexity of:
1.2 Preorder Traversal
A preorder traversal is another approach to visiting all the nodes in a binary tree in the following order :
Here, first, we need to visit the parent node, then visit the left child, and finally visit the right child.
1.2.1 Problem Description
In this problem:
We are given the root of a binary tree, root, and we want to traverse the tree in a preorder traversal approach.
1.2.2 Example
Input:
Output: [10, 8, 7, 6, 7, 5, 4]
1.2.3 Solution
If we use recursion to traverse this single-parent binary tree:
in a preorder fashion, then the code will look like the following:
def f(root):
# ......
result.append(root.val)
f(root.left)
f(root.right)
# ......We can see the above code has the same order as the preorder sequence. First, we stored the parent node value, then we call our recursive function for the left child, then for the right child.
The preorder traversal code will execute our main example as follows:
Let us see the complete code below:
def BT_preorderTraversal(root):
def traversal(root, result):
if not root: # is it an empty node?
return []
if not root.left and not root.right: # is it a leaf node?
return result.append(root.val)
if not root.left: # is it a parent node with a single right child?
result.append(root.val)
return traversal(root.right, result)
if not root.right: # is it a parent node with a single left child?
result.append(root.val)
return traversal(root.left, result)
result.append(root.val)
traversal(root.left, result)
traversal(root.right, result)
result = []
traversal(root, result)
return resultTime Complexity:
Every node will be visited one time, so the time complexity will be:
Space Complexity:
Also, Like inorder traversal, the space complexity will consist of the stack memory size ( an implicit memory that is allocated for recursive function calls) plus the size of the result list (which will store the nodes’ values). Then, that will result in the space complexity of:
1.3 Postorder Traversal
Finally, this is our last traversal problem that uses the recursion or depth-first approach to traverse a binary tree. Postorder traversal visits all the nodes in a binary tree in the following order :
Here, first, we need to visit the left child, then visit the right child, and finally the root (parent) node.
1.3.1 Problem Description
In this problem:
We are given the root of a binary tree, root, and we want to traverse the tree in a postorder traversal approach.
1.3.2 Example
Input:
Output: [7, 6, 8, 5, 4, 7,10]
1.3.3 Solution
If we use recursion to traverse this single-parent binary tree:
in a postorder fashion, then it will look like this:
def f(root):
# ......
f(root.left)
f(root.right)
result.append(root.val)
# ......First, we stored the parent node value, then we call our recursive function for the left child, then for the right child.
The postorder traversal code will execute our main example as follows:
Time Complexity:
Postorder traversal has also time complexity equal to:
Because every node will be visited one time.
Space Complexity:
And yes, the space complexity will consist of the stack memory size ( an implicit memory that is allocated for recursive function calls) plus the size of the result list (which will store the nodes’ values). Then, that will result in the space complexity of:
1.4 Level Order Traversal
Our last traversal approach for this post is level order traversal. This traversal is considered natural to our brains because It is how we would traverse a tree at first glance. The name “level” is because of how the algorithm traverses the tree level by level, and it does not consider the parent-child relationship structure.
Here is a simple visualization of how the level order traversal looks like:
1.4.1 Problem Description
In this problem:
We are given the root of a binary tree, root, and we want to traverse the tree in a levelorder approach.
1.4.2 Example
Input:
Output: [10, 8, 7, 7, 6, 5, 4]
1.4.3 Solution
To be able to traverse the list in that order, we need to use the Queue data structure. Why?
A very good question! You can notice that the visiting order of the level order approach is similar to how the Queue data structure handles its inputs and outputs:
Then, to traverse a tree in a level order approach:
First, we store the root node inside the queue.
Second, we loop over the queue elements (each a complete iteration over the queue = a complete loop over a tree level):
2.1 Remove a node from the queue.
2.2 Store the left child inside the queue if it exists.
2.3 Store the right child inside the queue if it exists.
3. Repeat step 2 if the queue is not empty.
Let us see how those steps could be translated into the code below:
def levelOrder(root):
if root is None:
return []
queue = deque()
result = []
queue.append(root)
while queue:
bag = [] # initialize a list to keep the track of the nodes at each level.
levels = len(queue)
for level in range (levels): # each complete iteration over the queue =
# full loop over a tree level
node = queue.popleft()
bag.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(bag) # store the nodes of each level inside result list.
return resultTime Complexity:
The Level order traversal has time complexity equal to:
Because every node will be visited one time.
Space Complexity:
Again, the space complexity will consist of the stack memory size ( an implicit memory that is allocated for recursive function calls) plus the size of the result list (which will store the nodes’ values) plus the size of the intermediate list bag ( a list to hold the nodes at each level). Then, that will result in the space complexity of:
1.5 Binary Tree Paths
Now, let us see how we can take the advantage of the traversal methods to get all paths in the tree. A tree path is:
A series of connected nodes start with the root node and end with a leaf node.
1.5.1 Problem Description
In this problem:
We are given the root of a binary tree, root, and we have to get all the possible paths in the tree.
1.5.2 Example
Input:
Output: [ “10 -> 8 ->7”, “10->8->6”, “10->7->5”, “10->7->4”]
1.5.3 Solution
The intuitive approach to solve this problem is by traversing this tree path-by-path. So, first, we start with the root node. Second, we go down the tree collecting the nodes along the path till we hit a leaf node (terminal node). Third, we store that path in the result list. But how can we do this? Yes, I hear it coming … “Can we use a DFS traversal approach, Waleed?”
Yes, it is the right question that has the right answer! we will use a preorder traversal approach, but instead of storing the node directly inside the result list, we will store it in a string variable path. Also, we can notice that the path variable was updated while being passed to the DFS function, so do not get confused if this is a preorder traversal approach or not.
Now, let us develop this recursive algorithm together:
Check if the node is empty like this blank image:
If it is True: We return an empty string
if root is None:
return ""2. Check if the node is a leaf node:
If it is True: It means we hit the bottom of the tree, so we need to store this path.
if not root.left and not root.right:
return result.append(path + str(root.val))3. Check if the node has no right child:
If it is True: We will call the recursive function on the left child.
if not root.right:
return get_path(root.left, path + str(root.val) + "->", result)4. Check if the node has no left child:
If it is True: We will call the recursive function on the right child.
if not root.left:
return get_path(root.right, path + str(root.val) + "->", result)Now, let us see the complete code:
def get_path(root, path, result):
if root is None:
return ""
if not root.left and not root.right:
return result.append(path + str(root.val))
if not root.left:
return get_path(root.right, path + str(root.val) + "->", result)
if not root.right:
return get_path(root.left, path + str(root.val) + "->", result)
get_path(root.left, path + str(root.val) + "->", result)
get_path(root.right, path + str(root.val) + "->", result)
result = []
get_path(root, "", result)
return resultTime Complexity:
The time complexity for this solution is:
Because every node will be visited one time.
Space Complexity:
The space complexity will be:
In this example, we used a result list to store the paths, and each path is a string with a length h, which is equal to n = the total number of nodes, in the worst-case scenario.
Break Time!
Now, I would like you to have a break before continuing the next part of this series. GO, GO, GO, and drink some water or juice, I’ll be waiting for you!
Ok ok ok, you could not resist skipping the break, but anyway welcome back again!
2. Boolean Problems
The second part of this post will focus on different types of binary tree problems. These types of problems require us to inspect the binary tree looking for some patterns, and if they exist, we will provide a boolean answer (True/False) as an output. So, let us see what this group holds for us!
2.1 Validate Binary Search Tree
Our first task in this section will be to validate a binary tree. We have to validate if this binary tree is considered a binary search tree or not. A binary tree is considered a binary search tree if:
The left subtree of the parent node has nodes with key values less than the parent node key’s value. In other words, all the nodes under the left subtree of a given parent node are less than the parent node.
The right subtree of the parent node has nodes with key values that are bigger than the parent node key’s value.
The left subtree and right subtree should also be binary search trees.
See how those subtrees under the root node follow these rules.
2.1.1 Problem Description
Given the root of a binary tree, validate if the binary tree is a binary search tree or not.
2.1.2 Example
Input 1:
Output: True
Input 2:
Output: False. 3 is the right child of parent node with key = 6, and it has a key value less than its parent, key = 6
Input 3:
Output: True
2.1.3 Solution
Based on the definition of a binary search tree, we can observe an interesting pattern in the order of the tree nodes. Let us take the following binary tree as an example:
If we unfold the right subtree of the root node and compare the nodes' values, we will have the following pattern:
node(4) < node(6) < node(8)
Then, if we apply that to the right subtree, we will have:
node(4) < node(6) < node(8) < node(15) < node(20) < node(25)
Now, let us include the root node to fit this order:
node(4) < node(6) < node(8) < node(10) < node(15) < node(20) < node(25)
This pattern could be summarized as:
Left child < Parent node < Right child
But wait, Waleed, this order looks familiar! Yes, glad you notice it. Let me help you :), It is the binary tree inorder traversal approach, wow! Thus, we can take this piece of information to our advantage. Now, we can say that a binary tree is NOT a valid binary tree if:
Left child ≥ Parent node
OR:
Right child ≤ Parent node
Then, our algorithm to solve this problem will be:
Traverse a binary tree in an inorder traversal fashion.
Store the nodes' values inside a list num.
Check if there are invalid node pairs, by comparing the list values:
A pair is invalid → if num[i] ≥ num[i+1].
Now, let us see the full code:
def isvalid_BT(root):
def Inorder(root, bag):
if not root:
return []
if not root.left and not root.right:
return bag.append(root.val)
if not root.left:
bag.append(root.val)
return Inorder(root.right, bag)
if not root.right:
Inorder(root.left, bag)
return bag.append(root.val)
Inorder(root.left, bag)
bag.append(root.val)
Inorder(root.right, bag)
bag = []
Inorder(root, bag)
for index in range(len(bag) - 1):
if bag[index] >= bag[index + 1]:
return False
return TrueTime Complexity:
The time complexity for this solution is:
Because every node will be visited one time.
Space Complexity:
However, the space complexity will be:
We use the num list to store the nodes' values for the linear checkup operation.
✏ ️Task: Can you optimize this space complexity?
2.2 Same Binary Tree
Alright, this is another boolean binary tree problem. In this problem, our job is to check if two binary trees are the same or not.
2.2.1 Problem Description
Given the roots of two binary trees, root₁, root₂, we have to check if the two trees are similar to each other or not.
2.2.2 Example
Input:
Output: False, The parent nodes of the right subtrees in the both trees, (20, 30) are not the same.
2.2.3 Solution
A simple solution to this problem will be to traverse both binary trees simultaneously and check if the values of each corresponding pair are the same. Let us break the code:
To check if both trees end at the same level:
if not root1 and not root2:
return True2. To check if there is dissimilarity in the binary trees' height.
if not root1 or not root2:
return False3. To check if there is an unmatching among key values of the binary tree.
if root1.val != root2.val: # check for the key values' similarity.
return FalseHere is the full code put together below :
def is_same_BT(root1, root2):
def check(root1, root2):
if not root1 and not root2: # check for the end of both trees.
return True
if not root1 or not root2: # Check for the heights' similarity.
return False
if root1.val != root2.val: # check for the key values' similarity.
return False
return check(root1.left, root2.left) and check(root1.right, root2.right)
return check(root1, root2)Time Complexity:
The time complexity for this solution is:
Where n = number of nodes in the first tree, and m = number of nodes in the second tree. In this case, every node in each tree will be visited one time, so in the worst-case scenario, we will be having two different trees, which yield this time complexity.
Space Complexity:
The space complexity will be:
which equals the size of the stack that needed to be allocated due to the recursive calls.
2.3 Symmetric Binary Tree
Here is another interesting version of binary tree similarity. Here our goal will be to check if the binary tree is symmetric or not. Let us take the following binary tree:
We can say this is a symmetric binary tree if:
The left child of the left subtree equals the right child of the right subtree.
left_child_node(7) of left_parent_node(8) = right_child_node(7) of right_parent_node(8)
2. The right child of the left subtree equals the left child of the right subtree.
right_child_node(5) of left_parent_node(8) = left_child_node(5) of right_parent_node(8)
In other words, if we draw a vertical line dividing the tree into two halves, both halves should mirror each other.
2.3.1 Problem Description
In this problem we:
Given the root of a binary tree, determine if it is symmetric binary tree or not.
2.3.2 Example
Input 1:
Output: True
Input 2:
Output: False. node(15) != node(7).
2.3.3 Solution
Based on the definition above, our algorithm can be developed simply. All we need is to check if the tree follows the conditions (1), and (2):
Check the similarity of the nodes' values (base condition):
if left.val != right.val:
return False2. Check condition (1), and condition (2):
return check(left.left, right.right) and check(left.right, right.left)Now, let us see the full code:
def is_symmetric_BT(root):
def check(left, right):
if not left and not right:
return True
if not left or not right:
return False
if left.val != right.val:
return False
return check(left.left, right.right) and check(left.right, right.left)
return check(root.left, root.right)Time Complexity:
The time complexity for this solution is:
Because every node will be visited one time.
Space Complexity:
And the space complexity will be:
which equals the size of the stack that needed to be allocated due to the recursive calls.
2.4 Balanced Binary Tree
This will be our last problem in this post, so shout out to you if you made it this far 👏.
In this problem, our task is to check if a binary tree is balanced or not. A binary tree is considered balanced if the difference between the height of the left subtree and the right subtree is no more than 1.
⚑ Remember
A binary tree height starts with 0 which belongs to the root node, i.e, 0,1,2,…etc.
2.4.1 Problem Description
Given the root of a binary tree, check if this binary tree is balanced or not.
2.4.2 Example
Input 1:
Output: False. we can observe that the left subtree (10) of root(20) has height = 3, comparing to the right subtree (30) of the root(20) which has height = 1.
Input 2:
Output: True.
2.4.3 Solution
Alright, this is an interesting problem, and its solution is as well! Let us take the following binary tree as an example:
Then, we can use the divide-and-conquer algorithm design paradigm to simplify this problem as follows:
A binary tree is balanced if :
The left subtree is balanced.
The right subtree is balanced.
The full tree (with the parent node) is balanced.
And based on the binary tree balance condition:
The difference between the height of the left subtree and the right subtree is no more than 1.
We can develop our algorithm much easier. Here are the steps:
Check the left subtree balance and return its height and a balance confirmation.
left_height_component = check_balance(root.left)2. Check the right subtree balance and return its height and a balance confirmation.
right_height_component = check_balance(root.right)3. Calculate the height difference of the full tree that includes the parent node.
difference = abs(left_height_component[1] - right_height_component[1])4. Subtrees are balanced If the left subtree is balanced and the right subtree is balanced.
balanced_childs = left_height_component[0] and right_height_component[0]5. A parent is balanced if the difference is at most 1.
balanced_parent = difference <= 16. A tree is balanced if the parent is balanced and its children are balanced.
balanced = balanced_childs and balanced_parentNow, let us see the full code:
def is_balanced_BT(root):
def check_balance(root):
if not root:
return [True, 0]
left_height_component = check_balance(root.left)
right_height_component = check_balance(root.right)
balanced_childs = left_height_component[0] and right_height_component[0]
difference = abs(left_height_component[1] - right_height_component[1])
balanced_parent = difference <= 1
balanced = balanced_childs and balanced_parent
return (balanced, max(left_height_component[1], right_height_component[1]) + 1)
if not root:
return True
is_balanced_tree = check_balance(root)[0]
return is_balanced_treeTime Complexity:
The time complexity for this solution is:
Because every node will be visited one time.
Space Complexity:
And the space complexity will be:
which equals the size of the stack that is needed to be allocated due to the recursive calls.
3. Family Patterns
The Binary Tree Family has provided us with some interesting problems which include one of the most important algorithm techniques, the Depth-First Search Approach (DFS).
As we noticed earlier in my previous post on the Combinatorics Family problems, the DFS technique was used to traverse a list of integers. In this family, we used the same approach to traverse binary trees. Here are some tips that can help you to apply DFS to any binary tree problem properly:
Define the return of an empty node:
We should define what the DFS function should return if we hit the bottom of the tree where there is no leaf node.
Here are some examples of potential returns:
For problems that require you to return an integer value → return 0
For problems that require you to return a real value → return 0.0
For problems that require to return list → return [ ]
For problems that require to return a list of lists → return [ [ ] ]
2. Define the return of a leaf node:
We should specify what the DFS function should return value if we hit the bottom of the tree where there is just a leaf node.
3. Define the return of a single child node (if necessary):
We should tell what should the DFS function do if it encounters a node with a single child.
4. Recap
Here are the main points of this post:
The Binary Tree is a type of data structure where data is organized as a tree.
Depth-First Search Approach is a popular method to traverse a binary tree.
Level order, inorder, preorder, and postorder traversals are popular binary tree traversal algorithms.
To apply DFS to a binary tree, we need to specify at least what the DFS function should return in the case of visiting an empty node or a leaf node.
5. Next Post
The next post will be talking about another branch of binary tree problems. In these types of problems, our task is to modify the structure of a binary tree according to some specific requirements, i.e., delete a single node, add a new node, or invert a binary tree completely. So STAY TUNED!
New to this series?
New to the “Unfold Algorithm Coding Interviews For Data Scientists” series? Start from the beginning, here [link to the series list]
Any oversights in this post?
Please report them through this Feedback Form, I really appreciate that!
Thank you for your reading!
You can learn more about the date of future posts for this series through my newsletter, where I talk about Algorithms, Machine Learning, and Data Science.
If you have any other questions or comments, please do not hesitate to share them with me through Newsletter | Medium | LinkedIn | Twitter. See you soon!
Resources
[1] Jitender Punia, Traversal of Binary Tree, 2022, Scaler.com.