How to find depth of binary tree


Maximum depth or height of a binary tree

Difficulty: Medium, Asked-In: Amazon, VMWare, Zoho, Synopsys

Key takeaway: One of the fundamental tree problems to learn problem-solving using DFS (Postorder traversal) and BFS traversal.

Let’s understand the problem

Given a binary tree, write a program to find its height.

  • The height or the depth of a binary tree is the total number of nodes or edges on the longest path from the root node to the leaf node. In other words, the height of a binary tree is equal to the largest number of edges or nodes from the root to the most distant leaf node.
  • The height of an empty tree is 0, and the height of a tree with one node is 1. 

Example

The leaf nodes of the binary tree are 5, 8, and 9.

  • For leaf node 5, the number of nodes along the edges is 4. 
  • For leaf node 8, the number of nodes along the edges is 4.  
  • For leaf node 9, the number of nodes along the edges is 3. 

The maximum number of nodes from root to farthest leaf = max(4, 4, 3) = 4. Hence, the height of the binary tree is 4. 

Discussed Solution Approaches

  • Recursive approach: Using DFS or Post-order traversal
  • Iterative approach: Using BFS or Level order traversal

Recursive approach: Using DFS or Post-order traversal

Solution Idea

A binary tree is a recursive structure where we can solve the problem using the solution of two smaller subproblems: left sub-tree and right sub-tree. So how can we apply this idea to find the height of a binary tree? Let's think!

Based on the definition, for finding the height, we should know the path length of the root to the deepest leaf node, which can be either present in the left-subtree or right sub-tree. In other words, the longest path from the root to the deepest leaf can go through either the left or right child of the root.

So the best idea would be to calculate the height of the left and right sub-tree recursively. Whichever sub-tree has the maximum height, we take that value and add 1 to get the height of the tree. Here is a clear insight:

The height of the tree = the longest path from the root node to the leaf node = 1 + max (longest path from the left-child to the leaf node, longest path from the right-child to the leaf node) = 1 + max (height of the left sub-tree, height of the right sub-tree)

So if we know the height of the left and right sub-tree then we can easily find the height of the tree. But one idea would be clear: before calculating the height of the tree, we must know the height of the left and right sub-tree. For this, we can use the post-order traversal. Think!

Solution Steps

Suppose we are using the function int treeHeight(TreeNode root).

  • If the tree is empty or root == NULL, we return 0 as the height of the given binary tree. This would be our base case.
  • Otherwise, we traverse the tree in a post-order fashion and call the same function for the left and right child to calculate the height of the left and right sub-tree.

    int leftHeight = treeHeight(root->left) int rightHeight = treeHeight(root->right)
  • Now after calculating the height of the left and right subtree, we take the maximum height among both and return the value by adding one to it.

    if (leftHeight > rightHeight) return (leftHeight + 1) else return (rightHeight + 1)

Solution Pseudocode

int treeHeight(TreeNode root) { if (root == null) return 0 else { int leftHeight = treeHeight(root->left) int rightHeight = treeHeight(root->right) if (leftHeight > rightHeight) return (leftHeight + 1) else return (rightHeight + 1) } }

Solution Analysis

We are doing post-order traversal for finding the height of the tree. So time complexity = O(n). Space complexity is equal to the size of the recursion call stack, which is equal to the height of the tree.

  • The best-case scenario occurs when the tree is balanced, or the tree's height is O(logn). So best case space complexity = O(logn)
  • The worst-case scenario occurs when the tree is highly unbalanced or skewed, i.e., there is only one node at each level. In this case, the height of the tree is O(n). So worst-case space complexity = O(n)

Explore this blog for better understanding: Recursive Tree Traversals of a Binary Tree

Iterative approach: Using BFS or Level order traversal

Solution Idea

Now a critical question is: can we find the height of the tree without recursion? Can we use level order traversal to find height? Let's think!

The idea is: while doing the level order traversal, whenever we move down to a level, we increase height by 1. We count the number of nodes at the current level, and using a loop, we start adding next-level nodes to the queue till the count of nodes at the current level is 0.

After this, we move to the next level and again increase the height by 1. In simple words, we continue a similar process whenever we encounter a new level in the tree. At the start, the value of height is initialized as 0.

Solution Steps

  1. We create a queue Q and push the root node into it. We also initialize a variable height with 0 to track the height of the tree.

    if(root == NULL) return 0 int height = 0 Queue Q Q.enqueue(root)
  2. Now we run a while loop till the Q becomes empty. In other words, this loop will explore every level. At each iteration of this loop:

    • We increase the height by 1 and store the count of the number of nodes at the current level in a variable nodeCount (equal to the current size of the queue).
    height = height + 1 int nodeCount = queue.size()
    • Now we insert children of all the nodes in the current level into the queue. For this, we run another loop till the nodeCount at the current level is 0. We check if the current node has the left and right children. If yes, we insert it into the queue.
    for(int i = 0; i < nodeCount; i = i + 1) { TreeNode temp = Q.dequeue() if(temp->left != NULL) Q.enqueue(temp->left) if(temp.right != NULL) Q.enqueue(temp->right) }
  3. If the queue is empty, it implies that the last level of the tree has been completely processed, and we return the value stored in the variable height.

Solution Pseudocode

int treeHeight(TreeNode root) { if(root == NULL) return 0 int height = 0 Queue Q Q.enqueue(root) while(Q.empty() == false) { height = height + 1 int nodeCount = Q.size() for(int i = 0; i < nodeCount; i = i + 1) { TreeNode temp = Q.dequeue() if(temp->left != NULL) Q.enqueue(temp->left) if(temp->right != NULL) Q. enqueue(temp->right) } } return height }

Solution Analysis

Time complexity = Time complexity of the level order traversal = O(n)

Space complexity = Space complexity of the level order traversal

  • The worst-case space complexity = O(n), when the tree is balanced.
  • The best-case space complexity = O(1), when the tree is highly un-balanced or there is only one node at each tree level.

Explore this blog for better understanding: Level Order Traversal of a Binary Tree

Critical ideas to think!
  • How can we solve this problem using iterative traversal using stack?
  • Can we solve this problem using pre-order or in-order traversal?
  • Can we think of implementing the BFS approach using some other technique? Can we use a NULL value to identify the new level in the tree?

Similar coding questions to practice

  • Find min depth of a binary tree
  • Merge Two Binary Tree
  • Count half nodes in a Binary tree
  • Count full nodes in a Binary tree
  • Deepest right leaf node in a binary tree
  • Get the level of a node in a binary tree
  • Check if two trees are identical
  • Print all nodes at distance K from a given node

Enjoy learning! Enjoy algorithms!

Height of a Binary Tree (Python Code with example)

 

A binary tree is a unique data structure adopted for data storage schemes in the field of computer science. Each node in a binary tree can have at most two children. Using a binary tree data structure is beneficial because it has the benefits of both an ordered array and a linked list, therefore, the time complexity for search is as fast as in a sorted array, and insertion or deletion operations are as swift as in a linked list. Example of a binary tree: 

How to find the Height of a binary tree?

The height of the binary tree is considered to be the longest path starting from the root node to any leaf node in the binary tree. If the target node for which we have to calculate height for, doesn’t have any other nodes connected to it, conclusively the height of that node would be 0. Therefore, we can say that the height of a binary tree is the elevation from the root node in the entire binary tree. In layman's terms, the height of a binary tree is equivalent to the largest quantity of the edges starting from the root to the most sparse leaf node in the binary tree.

A related concept in binary tree data structure is the depth of the tree. According to the definition of depth of a node in the binary tree is the total amount of edges starting from the root node to the destination node. Furthermore, the depth of a binary tree is the total amount of edges starting from the root node to the most far-flung leaf node. And in this article, we will learn how to find the height/max depth of a binary tree using recursion and without using recursion. 

Example

The figure below shows a binary tree with 4 levels indicated. 

 

The leaf nodes of the binary tree are : [70, 80, 50, 90] 

For the leaf node 70, the number of nodes along the edges is 4. 

For the leaf node 80, the number of nodes along the edges is 4. 

For the leaf node 50, the number of nodes along the edges is 3. 

For the leaf node 90, the number of nodes along the edges is 4.

The maximum number of node from root to farthest leaf is: max(4, 4, 3, 4) is 4. Hence, height of the binary tree is 4.  

Algorithm for Calculating Height of a Binary Tree

There are two methods to approach this problem statement. First Approach is based on Depth first seach using recursion, and the other method is based on Breadth first search using Level order traversal without using recursion. 

 

Finding The Height With Recursion (Depth First search approach)

Let us consider an example to understand the approach in an easier way. Consider the following Binary Tree, with ‘a’ as the root node and ‘h’, ‘e’, ‘f’ and ‘g’ as the leaf node: 

For the leaf node ‘h’, the number of nodes along the edges is 4. 

For the leaf node ‘e’, the number of nodes along the edges is 3. 

For the leaf node ‘f’, the number of nodes along the edges is 3. 

For the leaf node ‘g’, the number of nodes along the edges is 3.

 

The maximum number of node from root to farthest leaf is: max(4, 3, 3, 3) is 4. Hence, height of the binary tree is 4. 

Let us discuss the step-by-step implementation 

Step 1: Ask the root node, what is the height of the binary tree if the root node is ‘a’, and recursively the root node asks the same question to its left which is ‘b’ and right child which is ‘c’. And so on.  

 

 

Step 2: Recursively ‘b’ will do the same as the node ‘a’ and ask its left child ‘d’ and the right child ‘e’ what will be the height if you are the root node of the current binary tree, ie. 

Step 3: The node ‘d’ asks the same questions to it’s left and right child ie. 

The node ‘h’ does the same thing and now since the left node of ‘h’ is NULL it returns 0. 

Step 4: The node ‘h’ gives out the result of its left and right child, and after we find the maximum length between the leftHeight and rightHeight, where : 

leftHeight = 0 

rightHeight = 0

 

max(0, 0) = 0 

Therefore, at each iteration the node will return length: 1 + max(leftHeight, rightHeight)

Step 5: To get a better intuition of the algorithm, refer to the following image:

 

 

 Python Code (with Recursion): 

# define a Class Tree, to intiate the binary tree
 class TreeNode:
 def __init__(self, val):
 self. val = val
 self.left = None
 self.right = None
 
 def height(root):
 
 # Check if the binary tree is empty
 if root is None:
 # If TRUE return 0
 return 0 
 # Recursively call height of each node
 leftAns = height(root.left)
 rightAns = height(root.right)
 
 # Return max(leftHeight, rightHeight) at each iteration
 return max(leftAns, rightAns) + 1
 
 # Test the algorithm
 root = TreeNode(1)
 root.left = TreeNode(2)
 root.right = TreeNode(3)
 root.left.left = TreeNode(4)
 
 print("Height of the binary tree is: " + str(height(root)))
 

 

Output: Height of a simple binary tree:

 

Height of the binary tree is: 3

 

Time and Space Complexity:

The time complexity of the algorithm is O(n) as we iterate through node of the binary tree calculating the height of the binary tree only once.

And the space complexity is also O(n) as we are following recursion, where recursive stack can have upto n elements. 

Where n is the number of nodes in the binary tree.

 

Finding the Height Without Recursion (Breadth-First search approach)

Let us consider an example to understand the approach in a easier way. Consider the following Binary Tree, with 12 as the root node and 19, 16, 7 and 8 as the leaf node: 

 

For the leaf node 19, the number of nodes along the edges is 4. 

For the leaf node 16, the number of nodes along the edges is 3. 

For the leaf node 7, the number of nodes along the edges is 3. 

For the leaf node 8, the number of nodes along the edges is 3.

 

The maximum number of node from root to farthest leaf is: max(4, 3, 3, 3) is 4. Hence, height of the binary tree is 4.  

Let us discuss the step-by-step implementation 

 

Step 1: Use a queue data structure to approach this problem statement, hence, initialize an empty queue data structure.  

Set ‘ans’ variable to 0. 

 

ans = 0 

 

Step 2: Enqueue root node to the queue and process it in a while loop until there are no elements left and perform the same process for the other nodes, ie.  

Enqueue root node 12 

currSize = 1

 

Step 3: Run a while loop until currSize = 0, and till then keep dequeuing elements and after processing the elements when the value of currSize = 0, increment the value of ans

Therefore, dequeue 12, and check for its left child which is 13 and the right child which is 14, and enqueue them

Now:

currSize = 0

currNode = 12

Since, currSize = 0

ans = 1 

At next iteration currSize = 2 

Dequeue 13 and repeat steps 2 and 3 

Now:  

currSize = 1

currNode = 13 

Again, dequeue 14 and repeat steps 2 and 3 

Now: 

currSize = 0

currNode = 14 

Since, currSize = 0

ans = 2 

Follow, the steps repeatedly until there are no nodes to enqueue into the queue, after all the steps 

ans = 4 

 

Therefore, we receive ans = 4, ie height of the binary tree is 4.

Python Code (without Recursion): 
# Import Collections libaray to use Queue Datastructure
 import collections
 
 # define a Class Tree, to intiate the binary tree
 class TreeNode:
 def __init__(self, val):
 self.val = val
 self.left = None
 self.right = None
 
 def height(root):
 # Set result variable to 0
 ans = 0
 # Initialise the queue
 queue = collections.deque()
 # Check if the tree has no nodes
 if root is None:
 return ans
 
 # Append the nodes to queue and process it in while loop until its empty
 queue.append(root)
 
 # Process in while loop until there are elements in queue
 
 while queue:
 currSize = len(queue)
 # Unless the queue is empty
 while currSize > 0:
 # Pop elements one-by-one
 currNode = queue. popleft()
 currSize -= 1
 
 # Check if the node has left/right child
 if currNode.left is not None:
 queue.append(currNode.left)
 if currNode.right is not None:
 queue.append(currNode.right)
 
 # Increment ans when currSize = 0
 ans += 1
 return ans
 
 # Test the algorithm
 root = TreeNode(1)
 root.left = TreeNode(2)
 root.right = TreeNode(3)
 root.left.left = TreeNode(4)
 
 print("Height of the binary tree is: " + str(height(root)))
 

 

Output: Height of a simple binary tree:

 

Height of the binary tree is: 3

 

Time and Space Complexity:

The time complexity of the algorithm is O(n) as we iterate through node of the binary tree calculating the height of the binary tree only once.

And the space complexity is also O(n) as we are using an extra space for the queue.  

Where n is the number of nodes in the binary tree.

Applications of Binary Tree:

  1. Its used in many search applications and algorithms which constantly display and store data. For instance, map including set objects in many libraries.
  2. Its utilized in 3D video game to conclude which objects need to be executed.
  3. Its used in nearly every high-bandwidth router to store router tables.
  4. Its used in construction of compilers and (implicit) calculators to parse declarations.

Conclusion:

In this tutorial, we learned how to find the level order traversal of a binary tree, a basic introduction of binary trees and its applications. We also learned the meaning of height of a binary tree using two approaches, first where we apply depth first search using recursive and  in second approach we apply breadth first search without recursion using a queue data structure.

Basic idea of ​​binary tree implementation with Golang

For the general operations of the algorithm, there are none other than the three basic operations of writing, searching, and deleting. In addition, there may be some operations, such as obtaining information about the corresponding data structure. For example, a binary tree might need to get the degree of the tree, while stacks and queues might need to get the length.

According to this idea, we need to understand this to work with a binary tree:

  1. Define the structure of a binary tree
  2. Creating a binary tree
  3. Adding data to a binary tree
  4. Count the number of nodes in a binary tree
  5. Calculate the depth of a binary tree
  6. Binary tree traversal: four traversal methods
  1. Preliminary traversal: first visit the root node, then visit the left subtree, and finally visit the right subtree; this is repeated until the end.
  2. Traverse in reverse: first visit the left subtree, then visit the right subtree, and finally visit the root node; this is repeated until the end.
  3. Traverse in order: first visit the left subtree, then visit the root node, and finally visit the right subtree; this is repeated until the end.
  4. Hierarchical traversal: each level visits each node from left to right.

Binary tree structure.

Designing a binary tree structure. Use the characteristics of a one-way linked table and the similarity to a binary tree to design.

  1. The tree is a recursive form and is linked and stored between each node.
  2. Binary tree has only left and right subtrees
 type TreeNode struct { Data int // Used to store data Left *TreeNode // left subtree Right *TreeNode // right subtree Right *TreeNode // Right subtree } 

Creation of a binary tree.

The basic idea is to create a binary tree using the characteristics of a one-way chain table (in fact, it cannot be called a one-way chain table here, because it must be a one-way chain table; the root node points to two child nodes), so the nodes of the binary tree are the nodes of the chain table.

 func CreateNode(v int) *TreeNode { return &TreeNode{v, nil, nil} } 

Adding data to a binary tree.

The basic idea is to start with only one root node, then either towards the left subtree or towards the right subtree as needed, and just link directly to the new node, and so on and so forth.

 func InitTree() *TreeNode { root := CreateNode(1) //root node root.Left = CreateNode(2) //left subtree root.Right = CreateNode(3) //right subtree root.Left.Right = CreateNode(4) //right subtree of left subtree root.Right.Left = CreateNode(5) //left subtree of the left subtree of the right subtree root.Left.Left = CreateNode(6) root.Right.Right = CreateNode(7) return root } 

The schematic diagram of the result is as follows:

Counting the number of nodes in a binary tree.

We use the above example for testing purposes. Because a binary tree is a recursive structure, we can use recursion to bypass calculations.

 func (root *TreeNode) GetTreeNodeNum() int { if root == nil { return 0 } else { // calculate the number of nodes under the left node // calculate the number of nodes under the right node // and finally add the number of root nodes. return root.Left.GetTreeNodeNum() + root.Right.GetTreeNodeNum() + 1 } } 

Calculation of the depth of a binary tree.

Tree depth is also the maximum tree level.

The root node is the first level, and as long as a left subtree exists or a right subtree exists, the level must be added by one and the calculation continues to the end.

So this can be done again with recursion.

 func (root *TreeNode) GetTreeDegree() int { maxDegree := 0 if root == nil { return maxDegree } if root.Left.GetTreeDegree() > root.Right.GetTreeDegree() { maxDegree = root.Left.GetTreeDegree() } else { maxDegree = root.Right.GetTreeDegree() } return maxDegree + 1 } 

Traversal of four types of binary trees.

The first three are simple, using recursive methods, and the fourth method is more complex.

  1. Forward bypass

To traverse a binary tree in forward order, the following operations are performed:

  1. Visit the root.
  2. Traverse the left subtree of the root.
  3. Traverse the right subtree of the root.
 func (root *TreeNode) PreOrder() { if root != nil { // print root fmt.Print(root.data, " ") // print left tree root.Left.PreOrder() // print right tree root.Right.PreOrder() } } 

For the example above, the output should be 1 2 6 4 3 5 7 .

2. Post-order traversal

To traverse a binary tree in reverse order, the following operations are performed:

  1. Traverse the left subtree of the root.
  2. Traverse the right subtree of the root.
  3. Visit root.
 func (root *TreeNode) PostOrder() { if root != nil { // print left tree root.Left.PostOrder() // print right tree root.Right.PostOrder() // print root fmt.Print(root.data, " ") } } 

For the example above, the output should be 6 4 2 5 7 3 1 .

3. Unordered bypass

To traverse a binary tree, in traversal order, perform the following operations:

  1. Traverse the leftmost subtree.
  2. Visit root.
  3. Traverse the rightmost subtree.
 func (root *TreeNode) MidOrder() { if root != nil { // print left tree root.Left.MidOrder() // print root fmt.Print(root.data, " ") // print right tree root.Right.MidOrder() } } 

For the example above, the output should be 6 2 4 1 5 3 7 .

4. Bypassing the order of levels.

The main idea.

Since this is a tree structure and you want to display the results layer by layer, after outputting the value of the left node, you must output the value of the right node of this layer.

The previous three methods correspond to the "small three-node tree" model inference, so these three methods cannot immediately find the desired node in the neighborhood.

So we can consider creating a queue cache (first in, first out), traversing the data and putting it in the queue in output order.

So the solution is to implement each layer to access each node from left to right.

First, put the root node of the tree into the queue, you need to define the queue of the chain table.

Remove a node from the queue, print the value of the node first, if the node has a left subtree node, the left subtree is pushed onto the stack, if the node has a right subtree node, the right subtree is pushed onto the stack.

Repeat until there are no items left in the queue.

 func (root *TreeNode) LayerOrder() { if root == nil { return } // new queue queue := new(LinkQueue) // add root queue.Add(root) for queue.size > 0 { // Constantly out of queue element := queue. Remove() fmt.Print(element.Data, " ") // The left subtree is not empty and is in the queue if element.Left != nil { queue.Add(element.Left) } // The right subtree is not empty and is in the queue if element.Right != nil { queue.Add(element.Right) } } } 

Complete code for traversing a binary tree by levels.

 type LinkNode struct { Next *LinkNode Value *TreeNode } // Chained queue, first in first out type LinkQueue struct { root *LinkNode // Starting point of the chain table size int // Number of elements in the queue lock sync.Mutex // Locks used for concurrent security } // in func (queue *LinkQueue) Add(v *TreeNode) { queue.lock.Lock() defer queue.lock.Unlock() // If the top of the stack is empty, then add the node if queue.root == nil { queue.root = new(LinkNode) queue.root.Value = v } else { // Otherwise the new element is inserted at the end of the chain newNode := new(LinkNode) newNode. Value = v // Traverse all the way to the end of the chain nowNode := queue.root for nowNode.Next != nil { nowNode = nowNode.Next } // The new node is placed at the end of the chain nowNode.Next = newNode } // Number of elements in the queue +1 queue.size = queue.size + 1 } // func (queue *LinkQueue) Remove() *TreeNode { queue.lock.Lock() defer queue.lock.Unlock() // empty queue if queue.size == 0 { panic("over limit") } // pop the top element topNode := queue.root v := topNode.Value // Chain the top element's successor links queue.root = topNode.Next // Number of elements in the queue -1 queue.size = queue.size - 1 return v } 

Breadthwise binary tree traversal (BFS) in Python

Binary trees are forever. At least that's what the technical managers who hire developers think. And when you're asked to solve a binary tree problem in a technical interview, the first thing the interviewer wants to know is breadth or depth?

What's the difference?

When we talk about Breadth First Search (BFS) and Depth First Search (DFS), we mean the order in which the nodes of a binary tree are traversed. When walking in depth, you first descend to the bottom of the tree, and then go to the side, and when walking in breadth, on the contrary, you start from the root and descend first to its descendant nodes, bypass them, then descend to the descendants of descendants, bypass them, and etc.

Taking the binary tree in this figure as an example, the BFS approach would have the following order of traversal of nodes: 1, 2, 3, 4, 5.

In the case of DFS, there are different variants of the sequence of visiting nodes. It all depends on whether it will be a direct, reverse or centered traversal. For example, a forward traversal will return 1, 2, 4, 5, 3. We discussed these three types of traversal in the Python Binary Tree Traversal article.

Implementing breadth-first search in Python

Let's see how to make BFS in Python. Let's start by defining our TreeNode class. It should only contain the value and the left and right pointers.

 class TreeNode: def __init__(self, value): self. value = value self.left = None self.right = None 

1. Strategy

Here's how we'll traverse the nodes:

  1. Find the height of the tree from the root to the farthest leaf.
  2. Loop through all the levels (ending with the top).
  3. Walk through each level, outputting all nodes.

2. Finding the height of the tree

To go through each level, we first need to know how many levels there are in the tree. To do this, we will write a special method.

 def height(node): 

Yes, you guessed it: the method will be recursive, like most binary tree traversal methods. Let's think about what the base case will be. The easiest option is when we have a zero root. In this case, the height is 0. You might think that the simplest case is a node with no children, but then we have to check if there are children, and this already increases the complexity.

 def height(node): if not node: return 0 

What's next? We need to go around the left and right halves of the tree. We will call method height() for these halves and save to two variables: l_height and r_height .

 def height(node): if not node: return 0 l_height = height(node.left) r_height = height(node.right) 

Will we return left or right height? Of course, big! So we take max() of both values ​​and return it. Don't forget to add 1 for the current node.

 def height(node): if not node: return 0 l_height = height(node. left) r_height = height(node ​​right) return max(l_height, r_height) + 1 

3. Iterating levels in a loop

Now that we have the height, we can start writing a method to traverse the tree in width. The only argument this method will take is the root node.

 def breadth_first(root): 

Next we need to get our height.

 def breadth_first(root): h = height(root) 

Finally, we iterate over the height of the tree. At each iteration, we will call the helper function - print_level() , which takes node root and level.

 def breadth_first(root): h = height(root) for i in range(h): print_level(root, i) 

4.

Tree traversal

We will traverse each level separately, displaying all the nodes on it. This is where our helper function comes in handy. It takes two arguments: the root and the current level.

 def print_level(root, level): 

In this method, the level number is determined by index i loops for . To traverse the entire tree, we will recursively move through the levels, decrementing and , until we reach level 0. When we do, this will mean that we can now display the nodes on the screen.

Our base case is when the root is null . This method only prints the tree to the screen and doesn't return anything, so the base case would be just return .

 def print_level(root, level): if not root: return 

Next, if our level is 0 (that is, the level we are interested in), we need to print the value of this node.

 def print_level(root, level): if not root: return if level == 0: print(root.value) 

Finally, if the level number is greater than zero, that means we need to continue traversing the tree. We call our recursive method on the left and right halves of the tree. Don't forget to subtract one from level in both function calls.

 def print_level(root, level): if not root: return if level == 0: print(root value) elif level > 0: print_level(root.left, level - 1) print_level(root.right, level - 1) 

That's it! We had to create three different methods, but in the end we can walk the tree in breadth.


Learn more