Binary Tree (Part 1)

No introduction is needed for Binary Tree I guess because it's a very common data structure and an essential element of some advance binary tree based data structure like BST, Binary Heap, Binomial Heap, Fibonacci Heap, AVL, Red-Black Tree. Nevertheless I would just request you to recall basic properties of binary tree such as:

  1. Root node, left and right child
  2. Full Binary Tree
  3. Complete Binary Tree
  4. Perfect Binary Tree
  5. Balanced Binary Tree

In this article we won't go through any theory of binary tree but implementation of it. This article will contain following implementations:

  1. Pre-order traversal
  2. In-order traversal
  3. Post-order traversal
  4. Level order traversal
  5. Building binary tree from pre-order and in-order list
  6. Building binary tree from post-order and in-order list
Implementation:

A node of binary tree has three properties.

  1. Value of key
  2. Reference to left subtree
  3. Reference to right subtree
class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}

1. Pre order Traversal:

Recursive pre order traversal:

private void preOrderRecursive(Node node, List<Integer> list) {
    if(null == node) return;
    list.add(node.key);
    preOrderRecursive(node.left, list);
    preOrderRecursive(node.right, list);
}

Iterative pre order traversal:

public List<Integer> preOrderIterative() {
    List<Integer> list = new ArrayList<>();
    Stack<Node> nodeStack = new Stack<>();

    nodeStack.push(root);

    while (!nodeStack.empty()) {
        Node node = nodeStack.pop();
        list.add(node.key);

        if (null != node.right) nodeStack.push(node.right);
        if (null != node.left) nodeStack.push(node.left);
    }
    return list;
}

2. In order Traversal:

Recursive in order traversal:

private void inOrderRecursive(Node node, List<Integer> list) {
    if(null == node) return;
    inOrderRecursive(node.left, list);
    list.add(node.key);
    inOrderRecursive(node.right, list);
}

Iterative in order traversal:

public List<Integer> inOrderIterative() {
    List<Integer> list = new ArrayList<>();
    Stack<Node> nodeStack = new Stack<>();
    Node current = root;
    nodeStack.push(current);
    while (null != current.left) {
        current = current.left;
        nodeStack.push(current);
    }

    while(!nodeStack.empty()) {
        current = nodeStack.pop();
        list.add(current.key);

        if (null != current.right) {
            current = current.right;
            nodeStack.push(current);
            while (null != current.left) {
                current = current.left;
                nodeStack.push(current);
            }
        }
    }

    return list;
}

3. Post order Traversal:

Recursive post order traversal:

private void postOrderRecursive(Node node, List<Integer> list) {
    if (null == node) return;
    postOrderRecursive(node.left, list);
    postOrderRecursive(node.right, list);
    list.add(node.key);
}

Iterative post order traversal:

Need to implement

4. Level order Traversal:

public List<Integer> levelOrderTraverse() {
    List<Integer> list = new ArrayList<>();
    Queue<Node> Q = new LinkedList<Node>();
    Q.add(root);
    while(!Q.isEmpty()) {
        Node node = Q.poll();
        list.add(node.key);
        if(null != node.left) Q.add(node.left);
        if(null != node.right) Q.add(node.right);
    }
    return list;
}

5. Building binary tree from pre-order and in-order list:

// Consider this is global
int preIndex = 0;

private static Node buildTreeFromPreOrderInOrder(int[] preOrder, int[] inOrder, int inStart, int inEnd)  {
    if(inStart > inEnd) return null;

    Node node = new Node(preOrder[preIndex++]);

    if(inStart == inEnd) return node;

    int pos = searchCharPos(inOrder, inStart, inEnd, node.key);

    node.left = buildTreeFromPreOrderInOrder(preOrder, inOrder, inStart, pos-1);
    node.right = buildTreeFromPreOrderInOrder(preOrder, inOrder, pos+1, inEnd);
    return node;
}

private static int searchCharPos(int[] inOrder, int inStart, int inEnd, int value) {
    for(int i=inStart; i <= inEnd; i++)
        if(inOrder[i] == value) return i;
    return -1;
}

6. Building binary tree from post-order and in-order list:

// Consider this is global
int postIndex = 0;

private static Node buildTreeFromPostOrderInOrder(int[] postOrder, int[] inOrder, int inStart, int inEnd) {
    if(inStart > inEnd) return null;

    Node node = new Node(postOrder[postIndex--]);

    if(inStart == inEnd) return node;

    int pos = searchCharPos(inOrder, inStart, inEnd, node.key);

    node.right = buildTreeFromPostOrderInOrder(postOrder, inOrder, pos+1, inEnd);
    node.left = buildTreeFromPostOrderInOrder(postOrder, inOrder, inStart, pos-1);
    return node;
}
Full Code:
  1. BinaryTreeTraversal_Demo.java
  2. LevelOrderTraversal_Demo.java
Blog Comments powered by Disqus.

Next Post Previous Post