Binary search tree traversals

Most of the problems on binary search tree can be solved using one or other traversal of tree. There are three types of binary search tree traversals : Preorder traversal, Inorder traversal and Postorder traversal. Let’s discuss each one in detail.

Preorder traversal of BST

Preorder traversal means traverse the root node first, then left subtree and at last traverse right subtree. For example, given below tree, preorder traversal will be 10,5,1,,6,19,17,21.

binary search tree traversals

As we already know that binary search tree is recursive data structure, any traversal can be solved recursively. Start with the root, then do a preorder traversal of left subtree and then at last do the preorder traversal of right subtree.

In above example,  after traversing root node(10), left subtree is traversed in preorder [5,1,6]. Same is true after traversing node(5).

Preorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        System.out.println(root.value);
        if(root.right != null) inorder(root.right);
    }
}

Inorder traversal of BST

Inorder traversal means traverse left subtree first, then root node and at last traverse right subtree. For example, given below tree, inorder traversal will be 1,5,6,10,17,19,21.

preorder travesal binary search tree

Again following the recursive strategy, if node has left child, do inorder traversal on left subtree, once inorder traversal of left subtree is done, visit root node and then again do inorder traversal of right subtree.

In above example,  before traversing root node(10), left subtree is traversed in inorder [1,5,6]. Same is true before traversing node(5).

Inorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        System.out.println(root.value);
        if(root.right != null) inorder(root.right);
    }
}

Postorder traversal of BST

Postorder traversal means traverse left subtree first, then right subtree and at last visit root node. For example, given below tree, postorder traversal will be 1,6,5,17,21,19,10.

postorder traversal of binary search tree

Again following the recursive strategy, if node has left child, do postorder traversal on left subtree, then do postorder traversal of right subtree and finally visit root node.

In above example,  before traversing root node(10), left subtree is traversed in postorder [1,6,5] and then right subtree is traversed in postorder [17,21,19] and then finally node(10).

Postorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void preOrder(Node root){
        if(root == null) return;

        System.out.println(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }
}

In next few posts, we will discuss problems which can be solved using these traversals.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com