Learn Postorder Binary Tree Traversal by Solving Maximum Depth of a Binary Tree

Binary Trees are one of the common categories of datastructures to know for that comes up in coding interviews. No matter what type of questions get asked, to solve them, we usually have to traverse through everything in our given tree.

There are many ways to traverse through a tree but in this article, we will focus on learning how to do a postorder traversal of a binary tree by answering the LeetCode question, Maximum Depth of a Binary Tree.

Problem Statement

In the problem, we are given a binary tree and we want to find its maximum depth.

The tree is represented by multiple TreeNodes connected to each other.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

The maximum depth of a tree is the number of nodes is longest path from the root node down to the leaf node.

High Level Algorithm

Every TreeNode has two children, each of which has varying heights. We won’t be able to know the height of each node until we travel to the leaf node of a tree.

Once we reach the leaf node, we know that our height is 1. From there, we can start counting the heights of each of our TreeNodes as we go back up the tree.

Tree problems usually require usage of recursion. To write a recursive program, we always need to think about the base case (when we can stop traversing the tree) and the recursive case (where we process data and continue traversing the tree).

Base Case

The base case in this situation is when we reach the smallest height we can encounter. A tree with a height of 0 (a null Tree Node).

Recursive Case

The recursive case here is where we calculate the height of the left and right child node. This will continue until we hit our base case (null tree node) which will return us a height of 0.

The goal of the problem is to find the maximum height of the tree. Once we have the height of both the left and right child, we find the largest of the two and add 1 to include the current Tree Node itself.

What was described here is a Post Order traversal of a tree.

1. Get the height of the left child.
2. Get the height of the right child. 
3. Processing the height and return the maximum height back.

Implementation

class Solution {
    public int maxDepth(TreeNode root) {
        return helper(root);
    }
   
    private int helper(TreeNode root) {
        if (root == null) {
            // 1) base case
            return 0;
        } else {
            // 2) recursive case
            int left = helper(root.left);
            int right = helper(root.right);
            // 3) Process the result and return the max height back
            return Math.max(left, right) + 1;
        }
    }
}

Runtime and Space Complexity

Runtime

The runtime of this algorithm is O(N), because we have to explore every single Tree Node of this tree.

Space Complexity

The worst case space complexity of this algorithm is O(N). In the worst case, we will have a line of trees that only have one child and we would have to explore all of the Tree Nodes.

Conclusion

There are a couple of key lesson to be taken away from solving the Maximum Depth of a binary Tree:

1. How to do a DFS postorder traversal of a binary tree
2. How to bubble back up variable back up from a leaf node
3. How to define and create base and recursive case to handle recursion

While tree problems don’t get asked too often in coding interviews, trees are a subset of graph problems, which ARE common. Being able to handle recursion and bubbling up results will help you crack your next coding interview!