Striver’s Tree Series : Tree Data Structure

Striver’s Tree Series

In this post we will check “Striver’s Tree Series : Tree Data Structure”.

What is a tree data structure?

There are two major types of data structures:

  • Linear
  • Non-Linear

Tree is a Non-linear data structure where as Arrays, LinkedList are linear data structures. What makes tree a non-linear data structure is, the information or data is not stored in a sequential fashion, same is for traversal or retrieval.
Unlike, in arrays, we know that elements are stored at contiguous memory locations, however, it is not the same with trees. The nodes in a tree can be stored at random memory locations and can be linked to each other using pointers to define the structure of the tree.

Why is tree data structure important?

To understand why tree? Think about why we created other data structures. In order to do that, link every data structure to some real world entity and see where it fit’s well.

Will you use an array to store information of your family’s hierarchy? No right, what do you visualise this hierarchy as? I visualise it as a tree.

That is it, tree is used and important to store hierarchical data.

Tree data structure in C, C++, Java, Python

However, no data-structure is bound by any programming language. You can choose any of the above popular programming language and implement all possible trees in it. But, we highly recommend to go with any one of C++, Java or Python. These are object oriented language with a good number of inbuilt library functions.

Why Striver’s Tree Series?

This is sheet is prepared by Raj Vikramaditya A.K.A Striver, Candidate Master, 6*, who has bagged offers from Google Warsaw, Facebook London, He has also interned at Amazon India. He is also one of the top educators at Unacademy and was at GeeksforGeeks as well.

More over, these simple set of questions in the Striver’s Tree Series contains all important concepts required to excel in the Tree Data Structure.

Problems on Tree Data Structure:

  1. Inorder Traversal of Binary Tree
  2. Preorder Traversal of Binary Tree
  3. Post-order Traversal of Binary Tree
  4. Morris Preorder Traversal of a Binary Tree
  5. Morris Inorder Traversal of a Binary Tree
  6. Preorder, Inorder, and Postorder Traversal in one Traversal
  7. Right/Left View of Binary Tree
  8. Bottom View of Binary Tree
  9. Top View of Binary Tree
  10. Vertical Order Traversal of Binary Tree
  11. Root to Node Path in Binary Tree
  12. Maximum width of a Binary Tree
  13. Level order Traversal / Level order traversal in spiral form
  14. Height of a Binary Tree
  15. Diameter of Binary Tree
  16. Check if the Binary tree is height-balanced or not
  17. LCA in Binary Tree
  18. Check if two trees are identical or not
  19. Zig Zag Traversal of Binary Tree
  20. Boundary Traversal of Binary Tree
  21. Maximum path sum
  22. Construct Binary Tree from inorder and preorder 
  23. Construct Binary Tree from Inorder and Postorder
  24. Symmetric Binary Tree
  25. Flatten Binary Tree to LinkedList 
  26. Check if Binary Tree is the mirror of itself or not
  27. Check for Children Sum Property
  28. Populate Next Right pointers of Tree
  29. Search given Key in BST
  30. Construct BST from given keys
  31. Construct BST from preorder traversal
  32. Check is a BT is BST or not 
  33. Find LCA of two nodes in BST
  34. Find the inorder predecessor/successor of a given Key in BST. 
  35. Floor in a BST
  36. Ceil in a BST
  37. Find K-th smallest/largest element in BST
  38. Find a pair with a given sum in BST
  39. BST iterator
  40. Size of the largest BST in a Binary Tree 
  41. Serialize and deserialize Binary Tree
  42. Binary Tree to Double Linked List

Also checkout the Striver’s SDE Sheet to clear interviews of Amazon, Microsoft, or any other top tech startup.