Tree Data Structure - InterviewBit

Tree Data Structure

Implementation of BSTs

Walkthrough Examples:

VALIDBST INORDERNEXT

Examples

Next Greater Number BST

Tree Data Structure Problems

Bst traversal

Problem	Score	Companies	Time	Status
Valid BST from Preorder	100	Unbxd Inc.	62:49
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:09

Trie

Problem	Score	Companies	Time	Status
Xor Between Two Arrays!	150	Liv.ai	53:33
Hotel Reviews	200	Booking.com Fab	75:41
Shortest Unique Prefix	350		69:53

Simple tree ops

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

2 trees

Problem	Score	Companies	Time	Status
Merge two Binary Tree	200	Amazon	32:21
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	40:52
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:12
Vertical Sum of a Binary Tree	200	Amazon	29:15
Covered / Uncovered Nodes	200	Amazon	39:50
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:24
Cousins in Binary Tree	200	Amazon DE Shaw	60:00
Reverse Level Order	249	DE Shaw	26:21
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	64:05
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:44