### Traversals

Preorder (DFS)

- Operations order: root -> left -> right

Inorder (DFS)

- Operations order: left -> node -> right

Postorder (DFS)

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!

eg: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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

eg: https://www.geeksforgeeks.org/find-largest-subtree-sum-tree/

### Diameter of a Binary Tree

Longest distance between two nodes of a binary tree !

https://www.geeksforgeeks.org/find-maximum-path-sum-two-leaves-binary-tree/

### Lowest Common Ancestor

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

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