2 min read
- Operations order: root -> left -> right
- Operations order: left -> node -> right
Operations order: reft -> right -> root
Operations order: right -> left -> root [Reverse post order]
In all above we traverse a complete branch first!
Time complexity is O(N). Why? Recursion says time complexity should be 2^N
- There is only one choice go to its children
Prefer post-order traversal if not specified. The structure is similar to DP.
Calculate answers for children and from that answer for parents.
Level order (BFS)
We are going level by level!
Get these traversals right! Very important!
Construction of Binary Tree
You can construct a binary tree from any two traversals!
Linked List and Binary Tree
Sum on a Tree
When the sum is only from top to bottom
When the sum passes through a node
Diameter of a Binary Tree
Longest distance between two nodes of a binary tree !
Lowest Common Ancestor
So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.
Thank you, Have a nice day !!