BST Construction

Properties of BST:

  • Binary tree
  • Value of root node is greater than its left child and less than its right child

A tree Node:

var TreeNode = function (val) {
  this.val = val
  this.left = null
  this.right = null
}

Naive approach to construct a BST:

var root = new TreeNode(1)
root.left = new TreeNode(0)
root.right = new TreeNode(2)
root.left.left = new TreeNode(3)
root.right.right = new TreeNode(4)

Constructing BST from an array representing a tree:

Consider a tree:

           5
        /     \
       2       9
    /     \      \
    1     3       10

The above tree can be represented in an array like:

[5, 2, 9, 1, 3, null, 10]

Explanation:

  • The array starts with the root element 5, position i=0.
  • Any node’s left element = 2*i + 1
  • Any node’s right element = 2*i + 2
  • null value represents that the left child of 9 is empty.

Constructing a tree from this array:

function constructTree(arr, i) {
  if (i >= arr.length) return null

  var node = new TreeNode(arr[i])
  node.left = constructTree(arr, 2 * i + 1)
  node.right = constructTree(arr, 2 * i + 2)

  return node
}

var root = constructTree([5, 2, 9, 1, 3, null, 10], 0)

Written by Gagandeep Rangi who likes to talk about himself in third person. Twitter Instagram