Maximum Depth of Binary Tree Editorial

Practice Problem Link: Maximum Depth of Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, return its maximum depth.

The depth/height of a binary tree is the number of nodes from the root node to any of the leaf nodes. The maximum depth is the maximum of the depths across all the paths.

Approach (BFS)

The idea is to do a level order traversal of the tree and while moving from one level to another level increase the value of depth by one.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getMaxDepth(Node* root) {
    queue<Node*> treeNodes;
	treeNodes.push(root);
	int depth = 0;
	while (!treeNodes.empty()) {
		depth++;
		int nodesAtCurrentLevel = treeNodes.size();
		while (nodesAtCurrentLevel > 0) {
			Node* currentNode = treeNodes.front();
			treeNodes.pop();
			if (currentNode->left != NULL) {
				treeNodes.push(currentNode->left);
			}
			if (currentNode->right != NULL) {
				treeNodes.push(currentNode->right);
			}
			nodesAtCurrentLevel--;
		}
	}
	return depth;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	int getMaxDepth(Node root) {
		Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		int depth = 0;
		while (!treeNodes.isEmpty()) {
			depth++;
			int nodesAtCurrentLevel = treeNodes.size();
			while (nodesAtCurrentLevel > 0) {
				Node currentNode = treeNodes.peek();
				treeNodes.poll();
				if (currentNode.left != null) {
					treeNodes.add(currentNode.left);
				}
				if (currentNode.right != null) {
					treeNodes.add(currentNode.right);
				}
				nodesAtCurrentLevel--;
			}
		}
		return depth;
	}
}

Approach (DFS)

Calculate the maximum depth of the left subtree and the right subtree of the current root recursively. The maximum depth of the tree will be the maximum depth among the two subtrees + 1.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getMaxDepth(Node* root) {
    if(root == NULL) {
			return 0;
	}
	int leftSubtreeDepth = getMaxDepth(root->left);
	int rightSubtreeDepth = getMaxDepth(root->right);
	return max(leftSubtreeDepth, rightSubtreeDepth) + 1;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	int getMaxDepth(Node root) {
    	if(root == null) {
			return 0;
		}
		int leftSubtreeDepth = getMaxDepth(root.left);
		int rightSubtreeDepth = getMaxDepth(root.right);
		return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
	}
}