Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trees

Balanced Binary Tree

Medium · Trees · Asked at Amazon, Microsoft, Google, Adobe

A tree is balanced if, for every node, the heights of its left and right subtrees differ by at most 1. Print YES or NO.

Input

First line: k. Second line: k values — the tree in level order, -1 means no node.

Output

YES or NO.

Constraints

Return the height from a DFS, or -1 as soon as some subtree is unbalanced — O(n).

Example 1

Input

7
3 9 20 -1 -1 15 7

Output

YES

Example 2

Input

9
1 2 2 3 3 -1 -1 4 4

Output

NO

Hints

  1. Computing the height separately for every node repeats work — O(n²) on a skewed tree.
  2. Return the height from one DFS, or −1 to mean "already unbalanced". Stop as soon as a child returns −1 or the heights differ by more than 1.

Approach

check(node) returns the subtree height, or -1 if some node inside it is unbalanced. For a node: l = check(left) and r = check(right). If either is -1 or |l − r| > 1, return -1. Otherwise return 1 + max(l, r). Each node is processed once. The tree is balanced if check(root) != -1.

Complexity: O(n) time · O(h) recursion depth

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *left = nullptr, *right = nullptr;
    Node(long long v) : val(v) {}
};

// Build a tree from level order where -1 means "no node".
Node *readTree() {
    int k;
    cin >> k;
    vector<long long> v(k);
    for (auto &x : v) cin >> x;
    if (k == 0 || v[0] == -1) return nullptr;
    Node *root = new Node(v[0]);
    queue<Node *> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < k) {
        Node *cur = q.front();
        q.pop();
        if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
        i++;
        if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
        i++;
    }
    return root;
}

// height of the subtree, or -1 if it is not balanced
int check(Node *node) {
    if (!node) return 0;
    int l = check(node->left);
    if (l == -1) return -1;
    int r = check(node->right);
    if (r == -1 || abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}

int main() {
    cout << (check(readTree()) != -1 ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

sys.setrecursionlimit(100000)

class Node:
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None


def read_tree():
    """Build a tree from level order where -1 means "no node"."""
    data = list(map(int, sys.stdin.read().split()))
    k, v = data[0], data[1 : data[0] + 1]
    if not v or v[0] == -1:
        return None
    root = Node(v[0])
    q, i = deque([root]), 1
    while q and i < k:
        cur = q.popleft()
        if i < k and v[i] != -1:
            cur.left = Node(v[i])
            q.append(cur.left)
        i += 1
        if i < k and v[i] != -1:
            cur.right = Node(v[i])
            q.append(cur.right)
        i += 1
    return root


def check(node):
    """Height of the subtree, or -1 if it is not balanced."""
    if node is None:
        return 0
    l = check(node.left)
    if l == -1:
        return -1
    r = check(node.right)
    if r == -1 or abs(l - r) > 1:
        return -1
    return 1 + max(l, r)


print("YES" if check(read_tree()) != -1 else "NO")

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node left, right;
        Node(long v) { val = v; }
    }

    // Build a tree from level order where -1 means "no node".
    static Node readTree(Scanner sc) {
        int k = sc.nextInt();
        long[] v = new long[k];
        for (int i = 0; i < k; i++) v[i] = sc.nextLong();
        if (k == 0 || v[0] == -1) return null;
        Node root = new Node(v[0]);
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < k) {
            Node cur = q.poll();
            if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
            i++;
            if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
            i++;
        }
        return root;
    }

    // height of the subtree, or -1 if it is not balanced
    static int check(Node node) {
        if (node == null) return 0;
        int l = check(node.left);
        if (l == -1) return -1;
        int r = check(node.right);
        if (r == -1 || Math.abs(l - r) > 1) return -1;
        return 1 + Math.max(l, r);
    }

    public static void main(String[] args) {
        System.out.println(check(readTree(new Scanner(System.in))) != -1 ? "YES" : "NO");
    }
}

Solve Balanced Binary Tree online · All practice problems