Tree Data Structure - InterviewBit

Tree Data Structure

Binary Tree

Examples

Next Greater Number BST

Tree Data Structure Problems

Bst traversal

Problem	Score	Companies	Time	Status
Valid BST from Preorder	100	Unbxd Inc.	62:26
Kth Smallest Element In Tree	300	Amazon	29:17
2-Sum Binary Tree	400	Amazon	63:53
BST Iterator	500	Amazon	41:35
Recover Binary Search Tree	750	Amazon	66:03

Trie

Problem	Score	Companies	Time	Status
Xor Between Two Arrays!	150	Liv.ai	52:28
Hotel Reviews	200	Booking.com Fab	75:34
Shortest Unique Prefix	350		69:45

Simple tree ops

Problem	Score	Companies	Time	Status
Path to Given Node	200	Amazon	42:27
Remove Half Nodes	200	Amazon	47:20
Nodes at Distance K	200	Amazon	56:01
Last Node in a Complete Binary Tree	200	Flipkart	33:00
Consecutive Parent - Child	200	Unravel Data	20:01
Balanced Binary Tree	275	Amazon	30:19
Maximum Edge Removal	300	Amazon	56:03

2 trees

Problem	Score	Companies	Time	Status
Merge two Binary Tree	200	Amazon	32:09
Symmetric Binary Tree	300	Amazon Zomato	22:00
Identical Binary Trees	300	Amazon	11:36

Tree construction

Problem	Score	Companies	Time	Status
Construct BST from Preorder	200	clevertap	38:53
Inorder Traversal of Cartesian Tree	300	Amazon	51:21
Sorted Array To Balanced BST	300	VMWare Amazon	28:46
Construct Binary Tree From Inorder And Preorder	375	Amazon	47:03
Binary Tree From Inorder And Postorder	375	Amazon	50:43

Traversal

Problem	Score	Companies	Time	Status
Vertical Order traversal of Binary Tree	200	Amazon Grab infoworks	74:25
Diagonal Traversal	200	Amazon DE Shaw	49:04
Vertical Sum of a Binary Tree	200	Amazon	28:26
Covered / Uncovered Nodes	200	Amazon	38:39
Inorder Traversal	350	Amazon grofers	32:00
Preorder Traversal	350	Amazon	15:26
Postorder Traversal	350	Amazon juspay	31:28

Level order

Problem	Score	Companies	Time	Status
Right view of Binary tree	200	DE Shaw ThoughtWorks	31:22
Cousins in Binary Tree	200	Amazon DE Shaw	59:47
Reverse Level Order	249	DE Shaw	26:15
ZigZag Level Order Traversal BT	350	Amazon	42:13
Populate Next Right Pointers Tree	900	Amazon	50:58

Root to leaf

Problem	Score	Companies	Time	Status
Burn a Tree	200	Hippocabs Amazon	63:23
Max Depth of Binary Tree	350	Goldman Sachs Bloomberg FactSet Oracle	6:57
Sum Root to Leaf Numbers	350		45:33
Path Sum	350	Amazon DE Shaw	27:35
Min Depth of Binary Tree	350	Amazon	17:20
Root to Leaf Paths With Sum	350	Amazon	41:13

Inplace change

Problem	Score	Companies	Time	Status
Invert the Binary Tree	300		12:46

Tree search

Problem	Score	Companies	Time	Status
Least Common Ancestor	450	Adobe Amazon	57:33

Linkedlist tree

Problem	Score	Companies	Time	Status
Flatten Binary Tree to Linked List	500	Adobe Amazon	43:45

Segment tree

Problem	Score	Companies	Time	Status
Order of People Heights	700		76:32