13. Traversing and Building Binary Tree

 

Binary Tree Traversal

The process of visiting each node in a tree data structure, exactly once is called tree traversal.

Pre-order Traversal

• Check if the current node is empty or null.
• Display the data part of the root (or current node).
• Traverse the left subtree by recursively calling the pre-order function.
• Traverse the right subtree by recursively calling the pre-order function.

In-order Traversal

• Check if the current node is empty or null.
• Traverse the left subtree by recursively calling the in-order function.
• Display the data part of the root (or current node).
• Traverse the right subtree by recursively calling the in-order function.
• In a binary search tree, in-order traversal retrieves data sorted order.

Post-order Traversal

• Check if the current node is empty or null.
• Traverse the left subtree by recursively calling the post-order function.
• Traverse the right subtree by recursively calling the post-order function.
• Display the data part of the root (or current node).

import java.util.LinkedList;

import java.util.Queue;

class Node {

    int data;

    Node left;

    Node right;

    Node(int data) {

        this.data = data;

        this.left = null;

        this.right = null;

    }

}

class BinaryTree {

    void preOrder(Node root) {

        if (root == null)

            return;

        System.out.print(root.data + " ");

        preOrder(root.left);

        preOrder(root.right);

    }

    void postOrder(Node root) {

        if (root == null)

            return;

        postOrder(root.left);

        postOrder(root.right);

        System.out.print(root.data + " ");

    }

    void inOrder(Node root) {

        if (root == null)

            return;

        inOrder(root.left);

        System.out.print(root.data + " ");

        inOrder(root.right);

    }

    void levelOrderTraversal(Node root) {

        Queue<Node> queue = new LinkedList<>();

        queue.add(root);

        queue.add(null);

        while (!queue.isEmpty()) {

            Node node = queue.remove();

            if (node != null) {

                System.out.print(node.data + " ");

                if (node.left != null)

                    queue.add(node.left);

                if (node.right != null)

                    queue.add(node.right);

            } else if (!queue.isEmpty())

                queue.add(null);

        }

    }

}

Building Tree

To build a unique binary tree, in-order is required along with pre-order and post-order traversal of the tree.

class Node {

    int data;

    Node left;

    Node right;

    Node(int value) {

        this.data = value;

        this.left = null;

        this.right = null;

    }

}

class Tree {

    int firstIdx;

    int lastIdx;

    Tree(int[] inorder){

        this.firstIdx = 0;

        this.lastIdx = inorder.length - 1;

    }

    int search(int inorder[], int start, int end, int curr) {

        for (int i = start; i <= end; i++)

            if (inorder[i] == curr)

                return i;

        return -1;

    }

    Node treeUsingPreAndIn(int preorder[], int inorder[], int start, int end) {

        if (start > end)

            return null;

        int curr = preorder[firstIdx];

        firstIdx++;

        Node node = new Node(curr);

        if (start == end)

            return node;

        int pos = search(inorder, start, end, curr);

        node.left = treeUsingPreAndIn(preorder, inorder, start, pos - 1);

        node.right = treeUsingPreAndIn(preorder, inorder, pos + 1, end);

        return node;

    }

    Node treeUsingPostAndIn(int postorder[], int inorder[], int start, int end) {

        if (start > end)

            return null;

        int curr = postorder[lastIdx];

        lastIdx--;

        Node node = new Node(curr);

        if (start == end)

            return node;

        int pos = search(inorder, start, end, curr);

        node.right = treeUsingPostAndIn(postorder, inorder, pos + 1, end);

        node.left = treeUsingPostAndIn(postorder, inorder, start, pos - 1);

        return node;

    }

}