Binary Tree

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.

  • https://leetcode.com/problems/maximum-depth-of-binary-tree/

  • https://leetcode.com/problems/count-complete-tree-nodes/

• Level order (BFS)

  • We are going level by level!

  • https://www.geeksforgeeks.org/level-order-tree-traversal/

• 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

• https://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/

• https://www.geeksforgeeks.org/given-linked-list-representation-of-complete-tree-convert-it-to-linked-representation/

Sum on a Tree

• When the sum is only from top to bottom

  eg: https://leetcode.com/problems/path-sum-ii/

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