Tree — [Notes]
· When to use Trees?
· Tree Vocabulary
· Properties of Tree
· Types of Trees
· Binary Tree
· Full/Strict/Proper binary tree
· Perfect Binary Tree
· Complete Binary tree
∘ Perfect vs Complete Binary Tree
· Balanced Binary Tree
· Degenerate Or Pathological Tree
· Skewed Binary Tree
· Binary Search Trees
·
When to use Trees?
✅ Hierarchical data → File system
✅ Organizing data for quick search, insertion, deletion → Binary search trees
✅ Trie → Dictionary
✅ Network routing algorithm
Tree Vocabulary
Properties of Tree
✅ Recursive data structure
✅ Root is connected to subtrees
✅ Tree with N nodes will have N-1 edges
✅ Depth of x = length of path from root to x OR No. of edges in path from root to x
→ Depth of root = 0
Depth = length of path from root to x OR No. of edges in path from root to x
✅ Height of x = no. of edges in longest path from x to a leaf
→ Height of leaf Nodes = 0
Height = no. of edges in longest path from x to a leaf
Height of an empty tree = -1
Height of tree with 1 node = 0
Types of Trees
- Binary Tree
- Strict/Proper Binary tree
- Perfect Binary tree
- Complete Binary Tree
Binary Tree
A tree in which each node can have at most 2 children.
- Min Height =
floor(log₂n)
Max Height =n-1
- Time taken for an operation is proportional to height h
so, time complexity of operation is →O(h)
Best case →O(log₂n)
Worst case →O(n)
Full/Strict/Proper binary tree
each node can have either 2 or 0 children
Perfect Binary Tree
- A Binary tree is said to be Perfect Binary Tree, if all its internal nodes has exactly 2 children.
- In Perfect Binary Tree, all leaf nodes are on the same level or depth.
- Maximum no. of nodes in a binary tree with height h
= 2^(h+1) - 1
= 2^(no. of levels) -1 - Height of perfect binary tree with N nodes
✅ n = 2^(h+1) -1 ➡ 2^(h+1) = n+1 ➡ h = log₂(n+1)-1
Example → for n = 15, log₂(15+1) -1 → 4–1 = 3
Complete Binary tree
A Binary tree is said to be complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
- A Perfect Binary Tree whose rightmost leaves (perhaps all) on the last level have been removed is called Complete Binary Tree.
- Max no. of nodes at level i =
2^i - Height of complete binary tree ➡
floor(log₂n)
Perfect vs Complete Binary Tree
Some authors also refer Perfect Binary Tree as Complete Binary Tree. And they call Complete Binary Tree as Almost Complete Binary Tree or Nearly Complete Binary Tree. Any way, it doesn’t matter what name you give to these trees. You should just know the concepts.
Balanced Binary Tree
- Binary tree is called Balanced Binary Tree, if difference of left and right subtree height is maximum one for all the nodes.
- Height of tree at max —
log₂n, n = nodes - If any one node violates this rule i.e. Difference of left and right subtree height is more than one, then that tree is not balanced.
- diff = |height_left — height_right|
Degenerate Or Pathological Tree
A degenerate or Pathological Tree is a Tree where every parent node has only one child either left or right.
Such trees are performance-wise same as linked list. In fact, comparatively it provides slow performance than LinkedList as while traversing, you need to first check whether tree has left child or right child and then move to next node.
Skewed Binary Tree
A binary tree, which is dominated solely by left child nodes or right child nodes, is called a skewed binary tree, more specifically left skewed binary tree, or right skewed binary tree.
All Skewed trees are pathological trees, but all pathological trees are not skewed trees.
Binary Search Trees
- A binary tree in which for each node, value of all the nodes in left subtree is lesser or equal and values of of all the nodes in the right subtree is greater
