Balanced Tree

Medium

Unlock detailed company stats for this questionUpgrade

When using a tree data structure, it's common for the tree to become unbalanced over time due to the insertion order of nodes, which can in turn affect the performance of our programs. Let's define a balanced tree as one where the difference in height of the left and right subtrees is at most one, for all nodes in the given tree. Write a function is_balanced(node) that determines whether a binary tree is balanced or not.

Input: The root node of a binary tree

Output: True if the tree is balanced, False otherwise.

Assume you are given the root node of a tree that conforms to the following interface:


class Node {
  left: Node
  right: Node
  value: any
}

Examples

Example 1: Balanced


Tree:
      a
     / \
    b   c
   / \   \
  d   e   f

is_balanced(a) # => True

Example 2: Balanced


Tree:
     a
    / \
   b   c
        \
         d

is_balanced(a) # => True

Example 3: Not Balanced


Tree:
     a
    / \
   b   c
        \
         d
          \
           e

is_balanced(a) # => False

Example 4: Not Balanced


Tree:
      a
     / \
    b   c
   /     \
  d       e
 /         \
f           g

is_balanced(a) # => False

Note that while the last tree seems symmetrical, it is not balanced because nodes b and c are not balanced.

This is a classic data structures question that really tests your understanding of concepts like trees, recursion, and algorithmic runtime. The quality of being "balanced" is actually very important in real-world applications—that's why we created self-balancing variants such as b-trees and red-black trees.

The key to solving this problem is to read the prompt and examples carefully. Let's begin with the definition: "a balanced tree is one where the difference in height of the left and right subtrees is at most one, for all nodes in the given tree." Off the bat, we know we need to compare the height of the left and right subtrees. We also know we need to do this comparison for all nodes in the tree. Now the question is, how do we get the height?

Let's start off by writing a function to get the height of a tree. If you aren't certain what the "height" is, you could ask your interviewer to clarify. The height of a tree is typically defined as the maximum number of 'layers' from top to bottom.

Now, let's use this to implement our main function, is_balanced. All we have to do is explore each node and make sure the height of its subtrees meet the condition in the prompt: the difference in height should be less than or equal to 1.

A note on recursion: Whenever you implement a recursive function, in the back of your mind you should ask whether recursion is the best way to accomplish your goal. Recursion has the downside of using the callstack, which can lead to stack overflow for deeply nested data. You're unlikely to hit this error during an interview, but it's worth mentioning as a real-life constraint and explaining how to implement a non-recursive version (e.g. by using a stack).

Time Complexity: $O(n^2)$ . For each node, the get_height function is called to calculate the heights of the left and right subtrees. Since get_height is called for each of the n nodes in the worst case $O(n)$ , this results in $O(n * n) = O(n^2)$ time complexity.

Space Complexity: $O(h)$ . the space complexity is determined by the maximum depth of the recursion stack, which is the height of the tree ( $h$ ). Each recursive call of is_balanced adds to the call stack.

Optimized Approach

We can optimize the is_balanced function to reduce the time complexity to $O(n)$ by combining the height calculation and balance checking into a single traversal. Here’s how:

Interview experiences

1 shared

Uber · a year ago

"The process involved two coding rounds and a system design interview. The coding rounds went smoothly - I was comfortable with the data structures involved, including a question on binary indexed trees (Fenwick trees) for range sum queries. What didn't go well was the system design round; the interviewer gave very little feedback or direction, making it hard to gauge if I was on the right track. Communication from the recruiter between rounds was also slow."

Software Engineer · Mid Level / L4

Related courses

Course

Software Engineering Interview Prep

Land your dream software engineering role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates—practice data structures, algorithms, system design, people management, behavioral interviews, and more.

Course

System Design Interviews

Learn how to answer the latest system design questions across product, infrastructure, and AI domains. Features in-depth video examples, written breakdowns, and helpful reference patterns. Watch senior engineers and managers answer these questions in mock interview videos.

Balanced Tree

Roles

Companies

Categories