Data Structure - Binary Tree
Published: 2021-03-26 16:53:41

My summary of Leet Code [Binary Tree explore card](https://leetcode.com/explore/learn/card/data-structure-tree Also using GeeksforGeeks [Binary Tree articles](https://www.geeksforgeeks.org/binary-tree-data-structure/)

# Tree
> Each node of tree has root value and list of references to other nodes (called child nodes)

From a graph point of view

> directed acyclic graph which has N nodes and N-1 edges.

# Binary Tree

> tree structure where each node has at most two children. (left child & right child)

## Traversing a Tree
1. Pre-order (root, left, right)
2. In-order (left, root, right)
3. Post-order (left, right, root)
4. level-order traversal

This [article](https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846) provides a great overview of tree traversals and how they relate to BFS / DFS

### 1. Pre-Order Traversal
> 1. visit root
2. visit left sub tree
3. visit right sub tree

(root first, then left right children)
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/snem2prtcyx7wlh0nevq.png)
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hcgixpwtwvwcbtub18py.png)

#### Applications
1. used to create copy of a tree. 
2. get prefix expression of an expression tree. (e.g. Polish notation)

```
class Solution{
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> preorder(Node root) {
        if (root != null) {
            result.add(root.data);
        }
        if (root != null && root.left != null) {
            result.add(root.left);
        }
        if (root != null && root.right != null) {
            result.add(root.right);
        }
        return result;
    }
}
```

### 2. Post-order Traversal
> 1. visit left sub tree
2. visit right sub tree
3. visit root

(children left,right first, then root) 
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5pviogethigi7egs78bm.png)
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4kax0ul8c0otw3vqaxvb.png)

#### Applications
1. delete tree
2. get postfix expressions (e.g. reverse polish notation)

```
class Tree {   
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> postOrder(Node root) {
       if (root != null && root.left!=null) {
            postOrder(root.left);
        }
        if (root != null && root.right!= null) {
            postOrder(root.right);
        }
        if (root != null) {
            result.add(root.data);
        }
        return result;
    }
}
```
### 3. In-order Traversal
> 1. visit left subtree
2. visit root
3. visit right subtree

(left -> right, left root right)

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/61l8z23tpdtu49grie1e.png)
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3tiu3t86ckykanktvxqs.png)


#### Applications
1. in BST, inorder traversal gives nodes in non-decreasing order. 

```
class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> inOrder(Node root)
    {
        if (root != null && root.left!= null) {
            inOrder(root.left);
        }
        if (root != null) {
            result.add(root.data);
        }
        if (root != null && root.right!=null) {
            inOrder(root.right);
        }
        return result;
    }
}
```

### 4. Level order tarversal
traverse tree by level
> 1. visit root node
2. visit children of root node
3. visit children of children of root node
4. continue till leaf nodes 

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xw20fj57l8urf7harrvo.png)
 
#### Applications
1. BFS



### Traversal - Complexity
Time complexity: `O(1)`
Space Complexity: (consider size of stack for function calls)
Worst: `O(N)` (skewed tree)
Best: `O(log(n))` (balanced tree)

# Properties
#### 1. maximum number of nodes at height  *h* is 2<sup>h</sup>
level of root = 0
For root, h=0 and number of nodes is 2<sup>0</sup> = 1
Therefore number of nodes when h = *h* is 2<sup>h</sup>

#### 2. Maximum number of nodes in a BINARY tree of height *h* is 2<sup>h</sup> – 1. 
In binary tree node can only have at most two children.
keep in mind that height index of root is 0. But height *h* refers to the number of nodes from root to leaf. Therefore leaf nodes have height index of *h-1*. (something like array indexes VS array length)
So total number of nodes in tree is 
= 2<sup>0</sup> + 2<sup>1</sup> + 2<sup>2</sup> + ... + 2<sup>h-1</sup>
 = 1 + 2 + 4 + ... + 2<sup>h-1</sup>
 = 2 <sup>h</sup> - 1 (geometric series)

Mathematical proof for last line:
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jhwmy2ri3mp676gspuvt.png)
 

#### 3. In BINARY tree with N nodes, minimum possible height is log<sub>2</sub>(N+1). 

Using point above we know that 
2<sup>h</sup> - 1 = N
2<sup>h</sup> = N + 1
h = log<sub>2</sub>(N+1)

In Big O notation this is usually expressed as **O(log(n))**

#### 4. BINARY Tree with L leaves has at least |log<sub>2</sub>L|+ 1 levels
From point 1 we know that the number of leaf nodes are 2<sup>h-1</sup>.
2<sup>h-1</sup> = L
log<sub>2</sub>L = h - 1 
h = log<sub>2</sub>(L) + 1 

#### 5. In a full binary tree, the number of leaf nodes is always one more than nodes with two children.

more [here](https://www.geeksforgeeks.org/handshaking-lemma-and-interesting-tree-properties/)

# Binary Tree Types
1. Full Binary Tree
2. Complete Binary Tree
3. Perfect Binary Tree
4. Balanced Binary Tree
5. Degenerate / pathological tree

This [article](https://www.upgrad.com/blog/5-types-of-binary-tree/) gives a good description of each type of binary trees. and this [article](https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254) gives good illustrations of valid/ invalid types of binary treees. 

### 1. Full Binary Tree
> every node has either 0 or 2 children 

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hnhxtma1t2w8u6ycm5ky.png)
Here the number of leaf nodes (no children)  = number of internal nodes (2 children) + 1 

### 2. Complete Binary Tree
> All the levels are completely filled except the last level (level of height *h*) & last level has all keys as left as possible 

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cztu1d1vj90dooqhe0xg.png)
 

### 3. Perfect Binary Tree
> all the internal nodes have two children and all leaf nodes are at the same level. 
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0c9a0yf84dobkuzsxtvi.png)

Here, number of leaf nodes  = number of internal nodes + 1.
In perfect binary tree, number of nodes is maximum number of nodes 2<sup>h</sup> +1 
 
### 4. Balanced Binary Tree
Binary tree that is height balanced
> left and right subtrees of **every** node differ in height by no more than 1.

1. left and right subtrees' heights differ by at most one, AND
2. The left subtree is balanced, AND
3. The right subtree is balanced

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5gx8qypnknr3oah8h731.png)
In balanced tree, height is O(log(n))

### 5. Degenerate / pathological tree
> every parent node has 1 child

- behaves like linked list
- height is n
- worst case complexity basically super cursed 
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zo0d2jwq1ozxegnistqo.png)

# Binary Search Tree
Summary from LeetCode [Explore Card](https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/)
Its a binary tree satisfying binary search property
> special form of binary tree where: value in is node must be
greater than (or equal to) any values in its left subtree **AND** 
less than (or equal to) any values in its right subtree.


![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ophyioerlb6lu3feuxew.png)

## Traversal
same as binary tree only that:
> inorder traversal = ascending order 

## Search
> For each node:
1. if target value == node vale return the node 
2. if target value < node value search in left subtree
3. if target value > node value search in right subtree

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2da0ecg54n47uag4dlzu.png)
 

### Search - Recursive
```
public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        } else {
            if (root.val == val) {
                return root;
            } else if ( root.val > val ) {
                return searchBST(root.left, val);
            } else {
                // root.val < val
                return searchBST(root.right, val);
            }
        }              
    }
```
<u>Time Complexity </u>
time complexity is O(h) where h is height of binary tree
Height Balanced: `O(log(n))` 
Height Skewed: `O(n)` (n is the number of nodes in tree)

<u>Space Complexity</u>
More details in stack [overflow answer](https://stackoverflow.com/a/62604136)
Space complexity of tree: `O(n)`
Space complexity of recursive function is the height of the stack which would be the height of the binary tree.
Height Balanced: `O(log(n))`
Height Skewed: `O(n)`

### Search - Iterative
```
public TreeNode searchBST(TreeNode root, int val) {
    TreeNode init = root;
    while (init != null) {
        if (init.val == val) {
            return init;
        } else if (init.val > val) {
            init = init.left;
        } else {
            init = init.right;
        }
    }
    return init;
}
```
<u> Time Complexity <u/>
Height Balanced: `O(log(n))`
Height Skewed: `O(n)`

<u>Space Complexity<u/>
space complexity of tree: `O(n)`
Auxillary space complexity: `O(1)`


## Insert
Find proper leaf position for target node and insert node as a leaf.
> 1. search left or right subtrees (if node.value > target or node.value < target)
2. repeat step1 until reach a leaf node
3. add new node as its left / right child 

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c1gu025p8x0yga1modxs.png)
 

### Insert - Recursive
```
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        } else {
            return insert(root, root, val);
        }
        
    }
    
    public TreeNode insert(TreeNode root, TreeNode current, int val) {
        if (current.val < val && current.right != null) {
            return insert(root, current.right, val);
        } else if (current.val < val && current.right == null) {
            current.right = new TreeNode(val);
            return root;
        } else if (current.val > val && current.left !=null) {
            return insert(root, current.left, val);
        } else { // root.val > vall && root.left==null
            current.left = new TreeNode(val);
            return root;
        }
        
    }
```
<u>Time Complexity <u/>
Time complexity will be proportional to height.
Height Balanced: `O(log(n))`
Height Skewed: `O(n)`


<u>Auxillary Space Complexity</u>
Height of recursion stack ~ height of BST
Height balanced: `O(log(n))`
Height Skewed: `O(n)`


### Insert - Iterative
```
Node insert(Node root, int Key) {
    Node init = root;
    while (true) {
        if (init.data == Key) {
            break;
        } else {
            if (init.data < Key) {
                if (init.right != null) {
                    init = init.right;
                } else {
                    // init.right == null
                    init.right = new Node(Key);
                    break;
                }
            } else {
                // init.val > Key
                if (init.left != null) {
                    init = init.left;
                } else {
                    init.left = new Node(Key);
                    break;
                }
            }
        }
    }
    return root;
}
```

<u> Time Complexity </u>
Traversing BST. proportional to height of BST
Height Balanced: `O(log(n))`
Height Skewed: `O(n)`

<u>Auxillary Space Complexity</u>
Store current node. constant space
Complexity: `O(1)`

## Deletion
> 1. target node has **no child**: remove the node.
2. target node has **one child**: use child to replace itself.
3. target node has **two children**: replace the node with its in-order successor  / predecessor & and delete target node.

In-order successor: smallest node in right subtree
In-Order predecessor: biggest node in left subtree

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k2xz5v7oj00xf0yjqhhq.png)

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vdia9mbhr3j6m861959p.png)

```
class Tree {
    // Return the root of the modified BST after deleting the node with value X
	public static Node deleteNode(Node root, int X){
		// code here.
		Node pre = null;
		Node toDelete = root;
		while (toDelete != null && toDelete.data != X) {
		    pre = toDelete;
		    if (toDelete.data < X) {
		        toDelete = toDelete.right;
		    } else {
		        toDelete = toDelete.left;
		    }
		}
		if (toDelete == null) {
		    // node not found
		    return root;
		} else {
		   // delete node
		   if (toDelete.left == null && toDelete.right ==null) {
		       // no children
		       if (pre == null) {
		           return null;
		       } else {
		           if (pre.left == toDelete) {
		               pre.left = null;
		           } else {
		               pre.right = null;
		           }
		       }
		       
		   } else if (toDelete.left != null && toDelete.right != null) {
		       // two children
		       // inorder successor (smallest number in right subtree)
		       Node preSucc = toDelete;
		       Node successor = toDelete.right;
		       while (successor.left != null) {
		           preSucc = successor;
		           successor = successor.left;
		       }
		       toDelete.data = successor.data;
		       if (preSucc.left == successor) {
		           preSucc.left = null;
		       } else {
		           preSucc.right = null;
		       }
		   } else {
		       // onyl 1 child
		       Node child = null;
		       if (toDelete.left == null) {
		           child = toDelete.right;
		       } else {
		           child = toDelete.left;
		       }
		       if (pre.left == toDelete) {
		           pre.left = child;
		       } else {
		           pre.right = child;
		       }
		   }
		}
		return root;
	}
}
```
 



# Self-balancing Binary tree

## 1. AVL Tree 
> left subtree & right subtree height diff <= 1
After insert, if height difference > 1, rotations are performed to balance tree

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nhujkh068miwnmt2yffk.png)
 

## 2. Red-Black Tree 
> 1. each node painted red or black. 
2. root of tree is always black
3. red node cannot have red parent or red child
4. every path from node (incl. root) to any of the NULL nodes have same number of black nodes

balances by ensuring that a chai of 3 nodes never gets to form. 
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jtmgqixlv9jwhfv3n060.png)
 

Info from: [SO](https://stackoverflow.com/a/23277366)
- AVL more rigidly balanced -> provide faster look ups
- Insert intensive tasks -> red-black
- AVL may take more space. AVL store balance factor at each node (O(n)) space. for red-black if data stored in all nodes is >0. sign bit store colour information

Red-black is used for Java TreeMap & TreeSet


# Heap

## Binary Heap

1. min-heap
2. max-heap

> min / max -heap is complete binary tree where value of root node is <= / >= either of its children. Same property must be recursively true for **all** subtrees in binary tree.

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g4j33m4lnnxrmsnvgxfl.png)

### Analysis
- use when **ordering is important** (e.g. priority queue)
- good at doing comparative operations
e.g. if you want values above x. just grab all parents of node X. no need to do any traversals all the down to leaf nodes.

#### Lookup
unlike BST, left and right subtree has no meaning. you can't divide the tree to search it.
Must go through all nodes
Complexity: `O(n)`
 
<u>deletion<u/>: O(log(n))

#### Insertion: 
1. increase heap size by 1
2. insert new element at end of heap 
3. **Heapify**. let last node "bubbles up" (swaps with parents)
Complexity: `O(log(n))`
unlike BST, left and right subtree has no meaning. you can't divide the tree to search it.

#### deletion
1. replace root / element by last element
2. delete last element from Heap
3. **heapify** to ensure last node is in correct position

## Analysis
- insertion is better tha O(n)
- priority
- flexible size
- slow lookup. (fast if its finding max or min)


## Priority Queue

Queue is FIFO. Objects with higher priority that enter later and get out first.

> 1. every element has priority associated with it
2. element with high priority is dequeued befor an element with low priority
3. 2 elements have same priority they are served according to order in queue. 
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wkzqte7syyoihujl65ru.png)
 
e.g. emergency room

Heap can be represented in the form of an array. In binary heap priority queue, objects with higher priority would be higher up. 
Then look at binary heap as an array and dequeue objects.

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ik5gfaq0olb0uxoqbnt.png)

# Trie / Prefix tree
> specialized tree for searching text. 

can have >2 children. use to search if character in word exists / subword in word exists.

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vu4foiwjxnythtwta0bx.png)

Space advantage: since its a prefix tree, if words share same prefix, dont have to store it twice. 

### Search
Lookup for word. Look up for first character. then search children to see if other characters match.
Complexity is the height of the tree. 

Complexity: `O(log(n))` 

### Insertion
if character doesnt exist need to create new children. If character exists, mark end of word for last node. 

insertion requires one to go down depth of trie. 

Complexity: `O(log(n))`




 
# Reasons for using Trees
1. Store information that naturally forms hierarchy. Eg. the file system on a computer. 
2. Trees (e.g. BST) may provide moderately quick access/search.
Quicker than Linked List, slower than arrays. 
3. Trees provide moderate insertion/deletion,
Quicker than arrays, slower than unordered linked lists. 
4. No limit on number of nodes since nodes are linked using pointers (like linked list, unlike arrays)