Binary Tree

tejender7
Oct 4, 2022
4 min read

Updated: Feb 2, 2023

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent.

Each node has one item(value) and three pointers to other nodes: Parent, Left and Right.

Height and Depth

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.

Code for height of node:

get height(){
  if(!this.left && !this.right){
    return 0;
  }
  return Math.max(this.left ? this.left.height : 0, this.right ? this.right.height : 0) + 1;
}

The depth of a node is the length of the path to its root (i.e., its root path). When using zero-based counting, the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero.

Code for depth of a node:

get depth(){
  let depth = 0;
  let currentNode = this.parent;
  while(currentNode){
    depth++;
    currentNode = currentNode.parent;
  }
  return depth;
}

Traversal

Stepping through the items of a tree, by means of the connections between parents and children, is called traversing the tree, and the action is a walk of the tree. Often, an operation might be performed when a pointer arrives at a particular node.

1. In-Order Traversal - a traversal in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called an in-order traversal.

Code for In-Order Traversal

getInOrderTraversalArray(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  const leftArray = treeNode.left ? this.getInOrderTraversalArray(treeNode.left) : [];
  const rightArray = treeNode.right ? this.getInOrderTraversalArray(treeNode.right) : [];
  return [ ...leftArray, treeNode.item, ...rightArray ];
}

2. Pre-Order Traversal - A traversal in which each parent node is traversed before its children is called a pre-order traversal.

Code for Pre-order Traversal

getPreOrderTraversalArray(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  const leftArray = treeNode.left ? this.getPreOrderTraversalArray(treeNode.left) : [];
  const rightArray = treeNode.right ? this.getPreOrderTraversalArray(treeNode.right) : [];
  return [ treeNode.item, ...leftArray, ...rightArray ];
}

3. Post-Order Traversal - A traversal in which the children are traversed before their respective parents are traversed is called a post-order traversal .

Code for Post-order traversal

getPostOrderTraversalArray(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  const leftArray = treeNode.left ? this.getPostOrderTraversalArray(treeNode.left) : [];
  const rightArray = treeNode.right ? this.getPostOrderTraversalArray(treeNode.right) : [];
  return [ ...leftArray, ...rightArray, treeNode.item ];
}

Operations on a Binary Tree

Get left-most and right-most nodes from a node

In this example, we get the left-most node and right-most node from the root node: 1.

Code for left-most node and right-most node:

getLeftMostItemOfSubTree(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  if(!treeNode.left){
    return treeNode;
  }
  let currentNode = treeNode;
  while(currentNode.left){
    currentNode = currentNode.left;
  }
  return currentNode;
}

getRightMostItemOfSubTree(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  if(!treeNode.right){
    return treeNode;
  }
  
  let currentNode = treeNode;
  while(currentNode.right){
    currentNode = currentNode.right;
  }
  return currentNode;
}

Predecessor and Successor of a node in In-Order Traversal

In this example let's find out the predecessor and successor of node: 2

Predecessor: 4

Successor: 5

Code for Predecessor:

predecessorInOrderTraversal(treeNode){
  if(treeNode.left){
    return this.getRightMostItemOfSubTree(treeNode.left);;
  } else {
    let currentNode = treeNode;
    while(currentNode.parent.right !== currentNode){
      currentNode = currentNode.parent;
      if(!currentNode.parent){
        return currentNode;
      }
    }
    return currentNode.parent;
  }
}

Code for Successor:

successorInOrderTraversal(treeNode){
  if(treeNode.right){
    return this.getLeftMostItemOfSubTree(treeNode.right);
  } else {
    let currentNode = treeNode;
    while(currentNode.parent.left !== currentNode){
      currentNode = currentNode.parent;
      if(!currentNode.parent){
        return undefined;
      }
    }
    return currentNode.parent;
  }
}

Insertion

Insert before a node in In-Order Traversal:

Here we add 10 before 6 in In-Order Traversal

Code for Insertion before a node in In-Order traversal:

insertBeforeInOrderTraversal(treeNode, newNode){
  if(!treeNode.left){
    treeNode.setLeft(newNode);
  } else {
    const currentNode = this.getRightMostItemOfSubTree(treeNode.left);
    currentNode.setRight(newNode);      
  }
}

Insert after a node in In-Order Traversal:

Here we insert 10 after 2 in In-order traversal.

Code for Insertion after a node in In-Order traversal:

insertAfterInOrderTraversal(treeNode, newNode){
  if(!treeNode.right){
    treeNode.setRight(newNode);
  } else {
    const currentNode = this.getLeftMostItemOfSubTree(treeNode.right);
    currentNode.setLeft(newNode);
  }
}

Deletion

In deletion we have two conditions:

Node is a leaf node: In this case we just need to remove the node from the tree.
Node is not a lead: In this case we need to find a leaf node, swap items (values) between these two nodes and remove the leaf node from tree.

Code for deletion:

delete(treeNode){
  if(!treeNode.left && !treeNode.right){
    this.detachLeafNode(treeNode);
  } else if(treeNode.left){
    let currentNode = treeNode;
    let prevNode = treeNode;
    while(currentNode.left || currentNode.right){
      currentNode = currentNode.left ? this.predecessorInOrderTraversal(currentNode) : this.successorInOrderTraversal(currentNode);
      let temp = currentNode.item;
      currentNode.item = prevNode.item;
      prevNode.item = temp;
      prevNode = currentNode;
    }
    this.detachLeafNode(currentNode);
  } else if(treeNode.right){
    let currentNode = treeNode;
    let prevNode = treeNode;
    while(currentNode.left || currentNode.right){
      currentNode = currentNode.right ? this.successorInOrderTraversal(currentNode) : this.predecessorInOrderTraversal(currentNode);
      let temp = currentNode.item;
      currentNode.item = prevNode.item;
      prevNode.item = temp;
      prevNode = currentNode;
    }
    this.detachLeafNode(currentNode);
  }
}

detachLeafNode(treeNode){
  if(treeNode.parent.left === treeNode){
    treeNode.parent.left = undefined;
  } else if(treeNode.parent.right === treeNode){
    treeNode.parent.right = undefined;
  }
  treeNode.parent = undefined;
}

Real Life example of a Tree

File Manager is an example of a tree data structure where a folder has links to other files and folders (while can have further links to more files and folders).