# Binary Tree (Part 1)

#### 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

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;
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();

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);
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();

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);
}``````

Iterative post order traversal:

``Need to implement``

4. Level order Traversal:

``````public List<Integer> levelOrderTraverse() {
List<Integer> list = new ArrayList<>();
while(!Q.isEmpty()) {
Node node = Q.poll();
}
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;
}``````