Trees

Binary Trees

A type of tree in which each node has at most two children.

Implementation

Array

To get children of any node present at index i:

In 1-based index,

$left(i) = 2i$ $right(i) = 2i + 1$ In 0-based index, left(i) = 2i + 1$$$$right(i) = 2i + 2 To get to the parent of a node at i:

In 1-based index,

In 0-based index,

Types

• Full binary tree: Binary tree which has the maximum number of nodes for a given height.
• Complete binary tree:
  • Binary tree where all the nodes have 0 or 2 child and elements are filled from left to right.
  • Full binary tree until height h-1, at the last level elements are filled from left to right.
  • In array representation, complete binary tree won't have any gaps in the array

Traversal

DFS

Pre-order

Post-order

Level Order

public List<List<Integer>> levelOrder(TreeNode root) {
	Queue<TreeNode> q = new LinkedList<>();
	List<List<Integer>> result = new ArrayList<>();
	
	if(root==null) return result;
	
	q.add(root);
	
	while(!q.isEmpty()){
		List<Integer> level = new ArrayList<>();
		int levelLength = q.size();
		
		for(int i = 0; i<levelLength; i++){
			TreeNode node = q.poll();
			if(node!=null){
				level.add(node.val);
				
				if(node.left!=null) q.add(node.left);
				if(node.right!=null) q.add(node.right);
			}
		}
		result.add(level);
	}
return result;
}

Binary Search Trees

Special case of Binary trees.