Balanced Binary Search Tree Check

mediumSave

Binary Search TreeDepth-First SearchRecursionTree

Given the root of a binary search tree (BST), 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

[
  {
    "val": 3,
    "left": {
      "val": 9,
      "left": null,
      "right": null
    },
    "right": {
      "val": 20,
      "left": {
        "val": 15,
        "left": null,
        "right": null
      },
      "right": {
        "val": 7,
        "left": null,
        "right": null
      }
    }
  }
]

Output

true

Explanation. The given tree [3, 9, 20, null, null, 15, 7] is height-balanced.

Example 2

Input

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

Output

false

Explanation. The given tree [1, 2, null, 3, null, null, null, 4] is not height-balanced.

Follow-up: Could you solve the problem in O(n) time complexity where n is the number of nodes in the BST?

Constraints:

The number of nodes in the tree will be in the range [0, 5000].\nNode values will be integers.

Views: 3