Balanced Binary Tree

Balanced Binary Tree is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

Given a binary tree, determine if it is height-balanced.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4] Output: false

Example 3:

Input: root = [] Output: true

Constraints:

- The number of nodes in the tree is in the range [0, 5000].

- -104 <= Node.val <= 104

Topics and companies

Topics: Tree, Depth-First Search, Binary Tree.

Reported in interviews at Amazon.

How to practise Balanced Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes in the tree. Each node is visited exactly once. time and O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N. In the best case (balanced tree), H = log N. space.

Open Balanced Binary Tree in the code editor, or read the Balanced Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Balanced Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Postorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Balanced Binary Tree

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• All Nodes Distance K in Binary Tree — Medium, same subpattern
• Binary Tree Maximum Path Sum — Hard, same subpattern
• Binary Tree Postorder Traversal — Easy, same subpattern
• Delete Nodes And Return Forest — Medium, same subpattern
• Diameter of Binary Tree — Easy, same subpattern
• Find Leaves of Binary Tree — Medium, same subpattern