Tree Data Structure - InterviewBit

Tree Data Structure

Introduction to Tree Data Structure

Deepen your knowledge of Data Structures from the most commonly asked interview questions.

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:19
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	55:57

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:44
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:03
Vertical Sum of a Binary Tree	200	Amazon	28:25
Covered / Uncovered Nodes	200	Amazon	38:37
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