Balanced Binary Subtree

mediumSave

Binary TreeDepth-First SearchRecursionTree

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than one.

Example 1

Input

[
  {
    "value": 1,
    "left": {
      "value": 2,
      "left": null,
      "right": null
    },
    "right": {
      "value": 3,
      "left": null,
      "right": null
    }
  }
]

Output

true

Explanation. The tree has only three nodes and is automatically height-balanced.

Example 2

Input

[
  {
    "value": 1,
    "left": {
      "value": 2,
      "left": {
        "value": 4,
        "left": null,
        "right": null
      },
      "right": null
    },
    "right": {
      "value": 3,
      "left": null,
      "right": null
    }
  }
]

Output

true

Explanation. The tree is height-balanced, as the depth difference between the left and right subtree for every node is no more than 1.

Example 3

Input

[
  {
    "value": 1,
    "left": {
      "value": 2,
      "left": {
        "value": 3,
        "left": {
          "value": 4,
          "left": null,
          "right": null
        },
        "right": null
      },
      "right": null
    },
    "right": null
  }
]

Output

false

Explanation. The tree is not height-balanced because the node with value 2 has a left subtree with a height of 3 and no right subtree.

Follow-up: Can you improve your solution to be more efficient than O(n log n)?

Constraints:

The binary tree may have up to 5000 nodes.

Views: 2