Traversing binary trees.

  • 2
    Shares

Traversing a linear data structure is very simple as there are no child nodes for each node. But in the case of non-linear data structures such as a tree, there are child nodes. Thus traversing them makes a little complex and confusing. Let’s discuss various possible ways to traverse a tree in this post.

Meanwhile, if you are new to trees, sort yourself from my post here.

There are different ways to traverse a tree. They are

  1. Breadth-first search(BFS).
  2. Depth-first search(DFS).

1. Breadth-First Search:-

In the Breadth-first search algorithm, every level in the tree is traversed before going to the next level in the tree. In other words, we can say that all sibling nodes are read before reading the child nodes of a node.
Breadth-first search.
 
In the above example, there are three levels. Firstly the root value 10 is read. In the next level, the values 6,2 are read. Similarly from level 3, all the values 3,8,20 are read. 
 The pseudocode is as shown below.
Breath-first search pseudocode.
 
public ArrayList  breadthFirstSearch() {
        ArrayList < Integer > data = new ArrayList();
        ArrayList < Node > queue = new ArrayList();
        queue.add(this.root);
        while (!queue.isEmpty()) {
            Node currentNode = queue.get(0);
            data.add(currentNode.value);
            if (currentNode.left != null) {
                queue.add(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.add(currentNode.right);
            }
            queue.remove(0);
        }
        return data;
    }
breadthFirstSearch() {
        var data = [];
        var queue = [];
        queue.push(this.root);
        // var currentNode = this.root;
        while (queue.length != 0) {
            var currentNode = queue.shift();
            data.push(currentNode.val);
            if (currentNode.left) {
                queue.push(currentNode.left)
            }
            if (currentNode.right) {
                queue.push(currentNode.right)
            }
        }
        return data;
    }

2. Depth-First Search:-

Unlike the breadth-first search, the Depth-first search algorithm reads all the values formed by the child node and its child nodes before going to another direct child node. By observing the reading structure looks like reading the deepest node values. So it is called the depth-first search. 

Based on the order of traversing a node it’s further divided into 3 types.
  1. Death-First in order search.
  2. Depth-first pre-order search.
  3. Depth-first post-order search.
Every subtree in the binary tree can be visualized as shown below.
 
By using this pictorial representation we can remember and implement the Depth-first search easily.
Let’s look at all of them¬†one by one¬†with examples.
 

2.1 Depth-first pre-order search(NLR):-

In this approach, we read the node(N) first and process the left child node(L) of the node. Once the left child nodes are processed successfully then we traverse the right child node(R).

Please do remember that when processing the left and right nodes the same process will be repeated as discussed above.

The pseudocode is as shown below.

Depth-first pre-order-pseudocode
Implementations are as shown below.
public void depthFirstSearchPreOrderSearch(Node node) {
        if (node == null) {
            return;
        }
        System.out.println("value is:-" + node.value);
        depthFirstSearchPreOrderSearch(node.left);
        depthFirstSearchPreOrderSearch(node.right);
    }
depthFirstSearchPreOrderSearch(node) {
        if (node == null) {
            return;
        }
        console.log(node.val)
        if (node.left) depthFirstSearchPreOrderSearch(node.left);
        if (node.right) depthFirstSearchPreOrderSearch(node.right);
    }

2.2 Depth-first post-order search(LRN):-

In this approach, we read the left child node(L) of the node(N). Once the left child nodes processing completed successfully then we traverse the right child node(R). After processing both left and right child successfully then we read the value of the node(N)

Please do remember that when processing the left and right nodes the same process will be repeated as discussed above.

The pseudocode is as shown below.

Depth-first search post-order pseudocode.
 
The coding implementations are the same as we have seen above. It’s just that we need to interchange the printing lines.
public void depthFirstSearchPostOrderSearch(Node node) {
        if (node == null) {
            return;
        }
        depthFirstSearchPreOrderSearch(node.left);
        depthFirstSearchPreOrderSearch(node.right);
        System.out.println("value is:-" + node.value);
    }
depthFirstSearchPostOrderSearch(node) {
        if (node == null) {
            return;
        }
        if (node.left) depthFirstSearchPreOrderSearch(node.left);
        if (node.right) depthFirstSearchPreOrderSearch(node.right);
        console.log(node.val)
    }

2.3 Depth-first In-order search(LRN):-

In this approach, we read the left child node(L) of the node(N). Once the left child nodes processing completed successfully then we read the value if the node(N) After processing both left(L) and node(N) successfully then we read the values of the right child node(R).

Please do remember that when processing the left and right nodes the same process will be repeated as discussed above.

The pseudocode is as shown below.

Depth-first search in-order-traversal.

Coding implementation are

public void depthFirstSearchInOrderSearch(Node node) {
        if (node == null) {
            return;
        }
        depthFirstSearchPreOrderSearch(node.left);
        System.out.println("value is:-" + node.value);
        depthFirstSearchPreOrderSearch(node.right);
    }
depthFirstSearchInOrderSearch(node) {
        if (node == null) {
            return;
        }
        if (node.left) depthFirstSearchPreOrderSearch(node.left);
        console.log(node.val)
        if (node.right) depthFirstSearchPreOrderSearch(node.right);
    }

  • 2
    Shares