DEV Community

loading...

Binary Trees

ivywalobwa profile image Ivy-Walobwa ・4 min read

A binary tree is a sorted hierarchy of data.

It consists of;
1.A root node
2.0-2 children

The structure is such that the smallest values are on the left child node while the largest values on the right child node.

binary tree

Implementations

  1. Create the node class and binary tree class
class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree{
    constructor() {
        this.root = null;
    }
//add methods
}

Our node contains the data, left and right child. Our binary tree has a root node which is set to null.

2.Add methods to class

(i).Adding Data
We add data to the binary tree using a recursive algorithm.
case 1 -> empty tree: new node becomes the root node
case 2 -> smaller value: recursively added to the left
case 3 -> larger value: recursively added to the right
equal value -> treat as a larger value

add(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        }
        else {
            this._addTo(this.root, newNode);
        }
    }

    _addTo(currentNode, newNode) {
        if (newNode.data < currentNode.data) {
            if (currentNode.left === null) {
                //if new node is less than the current node
                //add to left
                currentNode.left = newNode;
            } else {
                this._addTo(currentNode.left, newNode);
            }
        } else {
            //if new node is greater than/ equal to the current node
            //add to right
            if (currentNode.right === null) {
                currentNode.right = newNode;
            } else {
                this._addTo(currentNode.right, newNode);
            }

        }
    }

I put an underscore before the addTo method to hint me that it is meant to act as a private method.

(ii).Searching

 //try find data in tree
    contains(data) {
        let current = this.root;
        let parent = null

        //while we don't have a match
        while (current !== null) {
            if (data < current.data) {
                //if value is less than current, go left
                parent = current;
                current = current.left;
            } else if (data > current.data) {
                //if value is greater than current, go right
                parent = current;
                current = current.right;
            } else {
                //we have a match
                break;
            }
        }
        return[ current, parent ];
    }
    find(data) {
     //return first value returned by contains() method
        return this.contains(data)[0];
    }

While implementing the remove operation, I realized I needed to check if the node to be removed exists and return the node and its parent. Adding the contains method saved me from duplicating code.
The contains method checks if a node exists and if it does, returns an array containing the found node and its parent.
The find method returns the first value of the array which is the node we are looking for.

(iii)Remove
This was honestly a tough one for me. Took me more than 8hrs to understand how it works.

A simple walk through before we jump into code 😉 .

find node to be deleted
    if node does not exists, exit
if node is terminal node
    remove parent's pointer to the deleted node
if node is not terminal node
    find the child to replace the deleted node 

Three scenarios in finding the child to replace deleted node:

1.Removed node has no right child - The left child replaces the removed node

binary tree

2.Removed node has a right child that has no left child - right child replaces the removed node

binary tree

3.Removed node has a right child which has a left child - the right child's left most child replaces the removed node

binary code

The code

  remove(data) {
        let parent = this.contains(data)[1];
        let current = this.find(data);

        if (current === null) {
            return false;
        }

        //CASE 1
        //removing node with no right child
        //its left child replaces the removed node
        if (current.right === null) {
            if (parent === null) {
                //if we are removing root node
                this.root = current.left;
            } else {
                if (parent.data > current.data) {
                    //make current left child, left child of parent
                    //rare case
                    parent.left = current.left;
                } else if (parent.data < current.data) {
                    //make current left child, right child of parent
                    parent.right = current.left;
                }
            }
        }

        //CASE 2
        //removing node whose right child has no left child
        //right child replaces the removed node
        else if (current.right.left === null) {
            //move removed node left child to the left of removed's right
            current.right.left = current.left;
            if (parent === null) {
                this.root = current.right;
            } else {
                if (parent.data > current.data) {
                    //make current right child a left child of parent
                    parent.left = current.right;
                } else if (parent.data < current.data) {
                    //make current right child a right child of parent
                    parent.right = current.right;
                }
            }

        }

        //CASE 3
        //if removed node's right child has a left child
        //replace removed with its right child's left most node
        else {
            //find right leftmost child
            let leftMost = current.right.left;
            let leftMostParent = current.right;
            while (leftMost.left != null) {
                //move to the left most node of the right child
                leftMostParent = leftMost;
                leftMost = leftMost.left;
            }
            //the parent's left subtree becomes the leftmost's right subtree
            leftMostParent.left = leftMost.right;
            //assign leftmost's left n right to current's left n right
            leftMost.left = current.left;
            leftMost.right = current.right;
            if (parent === null) {
                this.root = leftMost;
            }
            else {
                if (parent.data > current.data) {
                    //make leftmost the parent's left child
                    parent.left = leftMost;
                } else if (parent.data < current.data) {
                    //make leftmost the parent's right child
                    parent.right = leftMost
                }
            }
        }
        return true;

    }

(iv). Tree Traversal
Here we enumerate nodes in a well defined order.

Basic Algorithm;

Process Node
Visit left
Visit right

There are three common orders. They vary in the steps.

  • Preorder traversal
Process Node
Visit left
Visit right
  • Postorder traversal
Visit left
Visit right
Process Node
  • Inorder traversal
Visit left
Process Node
Visit right

The code

  //TREE TRAVERSAL
    preorder(current) {
        if (current === null) {
            return;
        }
        console.log(current.data);
        this.preorder(current.left);
        this.preorder(current.right);
    }

    postorder(current) {
        if (current === null) {
            return;
        }
        this.postorder(current.left);
        this.postorder(current.right);
        console.log(current.data);
    }

    inorder(current) {
        if (current === null) {
            return;
        }
        this.inorder(current.left);
        console.log(current.data);
        this.inorder(current.right);
    }

Sample test code

const tree = new BinaryTree();
tree.add(4);
tree.add(2);
tree.add(1);
tree.add(3);
tree.add(6);
tree.add(5);
tree.add(7)
tree.find(6);
tree.remove(6)

tree.postorder(tree.root) // 1 3 2 5 7 6 4
tree.preorder(tree.root) // 4 2 1 3 6 5 7
tree.inorder(tree.root) // 1 2 3 4 5 6 7

Note:Different helper methods can be declared as per requirements.

Discussion (0)

pic
Editor guide