Trees, Binary trees and Binary search trees.

trees representation.
  • 6
    Shares

Introduction to Trees:-

A tree is a non-linear data structure unlike a singly linked listdoubly linked liststacks or queues. The tree is a data structure in which nodes are connected in the parent/child relationship. 

The name tree itself explains a lot about it. It is exactly like a tree but in an inverted shape. Trees have a root which is divided into branches and these branches are further divided into branches till the end leaf. Similarly, In tree data structure there will be a root node and many other nodes are connected to it and the same shape is further repeated. Since a node has a connection with many other nodes thus making it a non-linear data structure. See some of the examples below.

Example tree-1
Example tree-2.
 

Tree terminologies:-

Node:- A node is a structure that may contain a value or condition, or represent a separate data structure.
Root:- The top node in a tree, the prime ancestor.
Child:- A node directly connected to another node when moving away from the root, an immediate descendant.
Parent:- The converse notion of a child, an immediate ancestor.
Siblings:- A group of nodes with the same parent.
Neighbor:- Parent or child.
Descendant:- A node reachable by repeated proceeding from parent to child. Also known as sub child
Ancestor:- A node reachable by repeated proceeding from child to parent.
Leaf / External node:- A node with no children.
Branch node / Internal node:- A node with at least one child.
Degree:- For a given node, its number of children. A leaf is necessarily degree zero. The degree of a tree is the degree of its root. The degree of a tree is The degree of the root.
Edge:- The connection between one node and another.
 

Some more terms….

Path:- A sequence of nodes and edges connecting a node with a descendant.
Distance:- The number of edges along the shortest path between two nodes.
Depth:- The distance between a node and the root.
Height:- The number of edges on the longest path between a node and a descendant leaf.
Width:- The number of nodes in a level.
Breadth:- The number of leaves.
Height of tree:- The height of the root node or the maximum level of any node in the tree.
Sub Tree:- A tree T is a tree consisting of a node in T and all of its descendants in T.
Ordered Tree:- A rooted tree in which ordering is specified for the children of each vertex.
Size of a tree:- Number of nodes in the tree.

 
Binary Tree:-
A binary tree is a type of tree in which each node has utmost 2 child nodes. Some of the examples are as shown.
binary tree example.
 
If you observe the node with data 1 has two child nodes holding 5,12. similarly 5 has two child nodes holding 6,3. But right child node 12 is holding the only node with value 11. By the definition of the binary tree, every node is having the utmost of 2 child nodes. So this is a binary tree.
Similarly, observe the example shown below. The node with data 2 has 4 child nodes. So it is not a binary tree.
Non-binary tree example.
 

Binary Search trees:-

A tree is called a binary search tree if and only if
  1.  Every parent node has the utmost of 2 child nodes.
  2.  each and every node to the left of the parent node should be less than the parent node.
  3.  Every node to the right of the parent node should be greater than the parent node.
For example:- 
binary search tree.
 
 Let’s implement a binary search tree.
Unlike SLL, DLL, stacks or queues, In trees, each Node has left and right node along with the data. In the implementation class, we don’t need head and tail nodes. A single node root is enough to traverse the entire binary search tree. Hence the initial code of the tree is as shown below.
 
class Node {
    int value;
    Node left;
    Node right;
    Node(Object value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class BinarySearchTree {
    Node root;
    public BinarySearchTree() {
        super();
        this.root = null;
    }
}
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null
    }
}

1. Insert:-

Insert operation inserts a new node in the appropriate position of the binary search tree. The thumb rule we need to remember always is to keep the smaller valued nodes on the left child and higher valued nodes on the right side. 

Observe the following examples. Firstly, let’s insert a value 45. Since 45 is greater than 15. So the right subtree is further evaluated. Now 45 is compared with 23. since 45 is greater than 23 again right subtrees is considered. Again 45 is compared with 71. Since 45 is less than 71 left subtrees is parsed. As part of comparison now 45 and 50 are compared. Since 45 is less than 50 and there are no nodes left on the left side of 50 a new node with value 45 is added. 

Similarly, By following the above process insertion of a node 75 happens as shown below.

If we convert the same logic into pseudocode, it will look like as follows.

BST insert pseudocode.
public void insert(int value) {
        Node newNode = new Node(value);
        if (this.root == null) {
            this.root = newNode;
        }
        else {
            Node currentPosition = this.root;
            boolean checkTrue = true;
            while (checkTrue) {
                if (value == currentPosition.value) {
                    checkTrue = false
//special case of having duplictes.  Its upto us on how to handle this.  We can manage a counter variable on the Node to see how many  number of time the value appeared.
                }
                if (value > currentPosition.value) {
                    if (currentPosition.right == null) {
                        currentPosition.right = newNode;
                        checkTrue = false;
                    }
                    else {
                        currentPosition = currentPosition.right;
                    }
                }

                if (value < currentPosition.value) {
                    if (currentPosition.left == null) {
                        currentPosition.left = newNode;
                        checkTrue = false;
                    }
                    else {
                        currentPosition = currentPosition.left;
                    }
                }
            }
        }
    }
insert(value) {
        var newNode = new Node(value);
        if (!this.root) {
            this.root = newNode;
        }
        else {
            var currentPosition = this.root;
            var checkTrue = true
            while (checkTrue) {
                if (value === currentPosition.val) {
                    checkTrue = false //special case of having duplictes. 
Its upto us on how to handle this. 
We can manage a counter variable on the Node to see 
how many number of time the value appeared.
                }
                if (value > currentPosition.val) {
                    if (currentPosition.right === null) {
                        currentPosition.right = newNode
                        checkTrue = false;
                    }
                    else {
                        currentPosition = currentPosition.right;
                    }
                }
                if (value < currentPosition.val) {
                    if (currentPosition.left === null) {
                        currentPosition.left = newNode
                        checkTrue = false;
                    }
                    else {
                        currentPosition = currentPosition.left;
                    }
                }
            }
        }
    }

To insert a new node we have to traverse a binary search tree for an appropriate position. In each iteration, we will be skipping half of the subtree. So the worst-case time complexity of insert operation is O(h) where h is the height of the tree. The height of a skewed tree may become n(When there are only left nodes or right nodes) and the time complexity will become O(n).

2. Remove:- 

Removing a node in a binary search tree has 3 cases.

1. When the node needs to be deleted is a leaf node:-
If the node is a leaf node then there is no problem. Since the leaf nodes don’t have any nodes associated with them we can simply make parent nodes left or right address to null. This is as shown below. 

BST remove leaf node illustration.

2. When the node needs to be deleted has one child node:-
This case is also fairly simple. Since every subtree is again a binary search tree, we can make the left or right address of the parent node of the node that needs to be deleted to the child node’s address of the node needs to be deleted.

BST remove the node with one child node illustration.

3. When the node needs to be deleted has 2 child nodes:-
This case is the complex case in removing a node from a binary search tree. The rule we need to remember all the time is that even after removing the node the tree still need to be a binary search tree. So the following process is followed.

The deleted node is replaced by either the largest value in the left subtree or the smallest value in the right subtree. 

BST remove leaf node with 2 child nodes illustration.

Note:- Here subtree should be considered from the node where the node is being deleted.

The coding implementation using matching all 3 cases using recursion is as shown below.

    public void remove(int value) {
        this.root = this.removeNode(this.root, value);
    }
    public Node removeNode(Node node, int value) {
        if (node == null)
            return null;
        else if (value < node.value) {
            node.left = this.removeNode(node.left, value);
            return node;
        }
        else if (value > node.value) {
            node.right = this.removeNode(node.right, value);
            return node;
        }
        else {
            if (node.left == null && node.right == null) {
                node = null;
                return node;
            }
            if (node.left == null) {
                node = node.right;
                return node;
            }
            else if (node.right == null) {
                node = node.left;
                return node;
            }
            Node aux = this.findMinNode(node.right);
            node.value = aux.value;
            node.right = this.removeNode(node.right, aux.value);
            return node;
        }
    }
    public Node findMinNode(Node node) {
        if (node.left == null)
            return node;
        else
            return this.findMinNode(node.left);
    }
    remove(value) {
        this.root = this.removeNode(this.root, value);
    }
    removeNode(node, value) {
        if (node === null)
            return null;
        else if (value < node.val) {
            node.left = this.removeNode(node.left, value);
            return node;
        }
        else if (value > node.val) {
            node.right = this.removeNode(node.right, value);
            return node;
        }
        else {
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            if (node.left === null) {
                node = node.right;
                return node;
            }
            else if (node.right === null) {
                node = node.left;
                return node;
            }
            var aux = this.findMinNode(node.right);
            node.val = aux.val;
            node.right = this.removeNode(node.right, aux.val);
            return node;
        }
    }
    findMinNode(node) {
        if (node.left === null)
            return node;
        else
            return this.findMinNode(node.left);
    }

3. Find:-

Searching value in the binary search tree is very simple compared to insert and remove operations and it’s efficient too. In each iteration, we will be skipping a level in the tree and reducing the search to half of the subtree. 

The pseudocode for the find operation is as shown below.

BST search pseudocode.

The implementation is as shown below.

    public Node find(int value) {
        if (this.root == null) {
            return null;
        }
        else {
            Node currentNode = this.root;
            boolean found = false;
            while (!found && currentNode != null) {
                if (value < currentNode.value) {
                    currentNode = currentNode.left;
                } else if (value == currentNode.value) {
                    found = true;
                } else {
                    currentNode = currentNode.right;
                }
            }
            if (found) {
                return currentNode;
            } else {
                return null;
            }
        }
    }
find(value) {
        if (this.root === null) {
            return undefined;
        }
        else {
            var currentNode = this.root;
            var found = false;
            while (!found && currentNode) {
                if (value < currentNode.val) {
                    currentNode = currentNode.left;
                } else if (value == currentNode.val) {
                    found = true;
                } else {
                    currentNode = currentNode.right;
                }
            }
            if (found) {
                return currentNode;
            } else {
                return null;
            }
        }
    }

The time complexity of the search operation is the same as the insert operation. In each iteration, we will be elimination a level from the height of the tree. But, for worst-case scenarios the height of the tree will be equal to the number of nodes in the tree. So the time complexity of the search operation of a binary search tree is O(n).

Use cases:-

  1. HTML DOM
  2.  Network routes.
  3. Folders in the operating system.
  4. Computer file systems,
  5. JSON representation of data, etc.

well, that’s it for now. In the next post, I will be writing about the traversal of the trees. Stay tuned for it.


  • 6
    Shares