Tempo

Question 1

Degree of a node is the number of children it has. Degre is 0 then leaf otherwise intermediate node

Question 2

Level order traversal

Answer 2

We initially enqueue the root into the queue. As we take out a node from the queue, we print it and enqueue it’s children into the q

Question 3

Level order traversal line by line

Answer 3

You can maintain a count variable which gives you the number of nodes int the current level. For that many time you can take out a node from the q, print it and enqueue its children. And then move to next line.

Repeat this while the q is not empty.
Outer loop travels through levels and inner loop travels through all nodes in a given level.

Method 2. Here we use end of level marker as null. ie when we have an entire level in the q, we add null to represent that the entire level is present. If we see null at top ofqueue, it means that the next level is now completely present in the . So we add null. And also print on next line.
As and when we take out a node from the q, we add it’s children. So when we encounter null we must have already added the children of all nodes present in that level.

Question 4

Size of bt

Answer 4

Size is the total number of nodes. So size of a tree will be the size of left subtree plus size of right subtree plus + 1. If root is null return 0

Question 5

Maximum in bt

Answer 5

If root is null return int-min. Else max is the maximum of root, maximum of left subtree nd maximum of right subtree

Question 6

Height of bt

Answer 6

If root is null return 0..

Else ht is Max of left and right ht +1

Question 7

Print nodes at distance k

Answer 7

We keep decrementing the value of k for each rec call and once we reach k=0, it means that we have to print it

If root is null return
If k is 0, print the node
Else solve(root-left, k-1)
Similarly for right

Question 8

Left view

Answer 8

Level order traversal

At each level only when I=0 print else proceed same as level order traversal

Question 9

Childsum

Answer 9

If root is null return true
If leaf node return true
Else check if root value is sum of its children as well as left subtree ischildsum and right subtree also satisfies childsum.
O total 3 cond

Question 10

Height balanced tree

Answer 10

Difference between left and right subtree heights should not be more than 1

Efficient solution would cal height in the same func rather than using a seperate function.

If root is null return 0
Int lh= is balanced (root->left)
If lh=-1 return -1
Int rh=is balanced (root-> right)
If rh=-1 return -1
If absolute difference is greater than 1 return -1
Else return height

Question 11

Convert bt to dll

Inorder traversal, inplace

Answer 11

Node* prev=null
Node* bttodll(node* root)
If root is null return broot.
Call the function on left subtree.
If prev is null it means we are on the left most node. So prev= root
Else 
Prev-> right= root
Root-> left = prev
Prev= root
Call the function on right subtree 
Return head

Question 12

By from inorder and preorder traversal

Answer 12

The first element of preorder is root
In inorder, the elements on to the left of this element form the left subtree and those on the right form the right subtree. So we recursively call on left and right subtrees.

We need to maintain 4 indices
Preindex, inindex, is ie.

If (is>ie) return null
Node* root = new node(pre[preindex++])

Now search for this root in inorder.
For (i= is to ie)
 If root, then inindex =i
Root-> left= func(is, inindes-1)
Root->right= func( inindex+1,ie)
Return root

Question 13

Spiral order traversal

Answer 13

Can push the elements of alternate rows on a stack during level order traversal and not print them as is. Once the level is over, we print them from the stack instead.
And negate reverse flag.

Method 2
Maintain 2 stacks S1 and S2
Push the root into S1.
While any of the two stacks is not empty do the following.
While S1 is not empty, take out a node print it and push children of taken out node into S2
While S2 is not empty, tke out a node print it and push children of taken out nodes in reverse order in s1

Question 14

Diameter of binary tree

The number of nodes present in the longest path present between two leaf nodes

Answer 14

D1= 1+ ht of left subtree +ht of right subtree
D2 is diameter of left subtree
D3 of right subtree
Diameter is the max of these three

Question 15

Lca

Answer 15

We need to find the path from root to n-1 using any of the traversal.
Using the same traversal find path from root to n2
Now when we have the paths, the element before the first element where ther is a mismatch is the lca.
If either node doesn’t exist then findpath returns false. If such is the case we return null.

To find path
If root is null return false
Else push root into vector 
If root is n return true
If (find path f left or right) then return true
Pop pushed element from the vector
This is used for eliminating paths which do not contain the node. 
Return false

Lca single traversal
We do normal recursive traversal. We have 4 cases
If root is same as N1 or n2 return root
If one of it subtree contains N1 and the other n2 then this root is lca
If one of its subtree contains both, return lca of that subtree
If none of its subtrees contain N1 and n2 return null

Question 16

Serialisation

Answer 16

We use -1 for null. Assuming -1 is not present in the tree as data
If(root is null) array push back null and return
Else array . pushback root data
Serilize (root-> left, are)
Similarly right

Question 17

Deserialisation

Answer 17

If index== arr.size return null
Int vl= arr[index]
Index++
If Val is -1 return null
Node* root= new node(Val)
Root-> left= deserialize(arr)
Root -> right similarly
Return root

Here index is global variable

Question 18

Kth smallest number

Answer 18

Global variable ans
We know that inorder traversal of BST is in increasing order or sorted. So to find the the kth smallest number we do inorder traversal . doing so We first reach the leftmost element from there we increment the count. Once count reaches k we set and to the value of that node.

If root is null return
Else
Func( root->left, k, count)
If count==k
 Ans=root->Val
 count= int_min
 Return
Count++ for root
Func(root-> right, k , count)

Question 19

2 sum bt

Answer 19

Maintain an unordered set. Do inorder traversal and for each node check if sum-root->Val is present in the set. If yes, the we found pair.
Else insert root to set
And call right subtree

Question 20

Recover BST

Two elements of a BST are swapped by mistake. Correct them to recover bst

Answer 20

We know inorder traversal of bst is in sorted array. So now when we try to to traverse at two instances the elements will not be in increasing order. Those will be our first and second nodes. Once found we just have to swap them.

Global variables prev, first second. 
If root is null return
FixBST( root-> left)
If( prev!=null and root->Val < prev-> Val) 
If first is null then first is prev
Second is root
Prev=root
FixBST (root->right)

If root is not satisfying BST property that it should be greater than prev, then prev is the first occurance. Because we need to check arr[i] and arr[i+1]. Since are doing inorder traversal we will not have i+1 so we instead check for i-1 and i. If not satisfying then prev is first occurance
But why second is root and not prevv?

There are two cases. When the first and second are not adjecent in the inorder traversal. In this case when first violation occurs first is prev. But when second violation occurs second will be at root only.
Next when the two are adjecent. In that case when the first violation occurs only prev is first and as always second is root.

Question 21

Sum of root to leaf nodes

Each root to leaf path can represent a number. Return the sum of all such numbers

Answer 21

DFS( root, Val)
Val*=10
Val+=root-> Val
Val%=1003
If leaf node add this number to answer and return 
// Should not make Val 0 cause it should retain its value when we backtrack 
Else
DFS ( root->left, Val)
DFS(root-> right, Val)

Question 22

Path sum

Given a BST and a sum, determine if there is a path with given sum

Answer 22

Global variable ans
Void DFS( root, Val, sum)
If not root return 
Val+=root->Val
If leaf node check if Val is equal to sum
Else 
Call DFS(root->left, Val, sum)
DFS(root-> right, Val, DFS)

Again no making Val zero cause it needs to retain its value while backtracking.

Question 23

Minimum depth of a bt

Answer 23

Void DFS(root, count)
If not root return
If leaf node then and is Max( ans, count) 
Count++
DFS(root+> left, count)
Similarly right

Question 24

Path to given node

Answer 24

DFS( root, b, v, &ans)
Not &v so v is retained to its original form after a recursion call . The form it was present before making recursion call
If not root return
V.push_back( root ->Val)
If  root equals b then ans is v return
Else  
DFS on left and right children

Question 25

Remove half nodes in a tree You have to remove all half nodes in a a tree and return the final bt. Half nodes are nodes which have it one child. Leaves should not be touched as they have both nodes as null

Answer 25

``` If root is null return null Remove half nodes in left subtree Remove half nodes in right subtree If leaf node then return root If current node is half node with left child null, then its right child is returned and replaces it in the tree If (rooot-> left== null) Node* new_root is root->right Free(root) return new root ``` ``` If curr node is half child with right node null then its left child replaces it in the tree If right child null Node* new node=root-> left Free(root) Return new node ```

Question 26

Morris traversal

Question 27

Inorder traversal of Cartesian tree Given an inorder traversal of a Cartesian tree, construct the tree. Cartesian tree is a heap ordered bt, where each node is greater than its children

Answer 27

``` Node* tree( root, start, end) If start>end return Maxi=int_min, index=-1 For( i = start to end) Find maximum element If node is greater than maxi Update and store index Node * root = new Node( maxi) Root-> left=tree(node, start, ind-1) Root-> right = tree( node, IND+1, end) ```

Question 28

Binary tree from inorder and postorder traversal

Answer 28

Note that the last element of post order traversal gives the root. To know the left and right subtrees, we can find the root in inorder , and elements on the left belong to left subtree and those on the right belong to right subtree. Now if we can somehow figure out the post order traversal for the subtrees, then the question boils down to the question again on the subtrees. The number of elements on the left subtree is equal to rootindex-inorderstart-1 So the first these many elements of the postorder traversal belong to left subtree and the rest to right subtree Initially traverse the inorder array and store the indices of elements in a map. Then Root = po(pe) ri=hm[root] Node* left= bt(in, is, ri-1,po, ps, ps+ri-is-1, hm) Node* right= bt(in, ri+1, ie, po, ps+ri-is, pe) Root->left= left Similarly right

Question 29

Merge two binary trees You need to merge them into a single bt. If 2 nodes overlap, then sum of node values is the new Val. Else whatever is not null

Answer 29

``` If not a return b If not b return a A-val+=b-->Val A-left=solve( a arrow left, b arrow left) Similarly right Return a ```

Question 30

Symmetric bt | Check if the given tree is a mirror image of itself

Answer 30

If (!root1) ret !root2 If(!root2) ret !root1 Ret ( values equal and f(root1- left, root2 right) and f( root1-right, root2 left)

Question 31

Invert a binary tree | Making left child right and right child left

Answer 31

If not of root return Invert left subtree Invert right subtree Now swap the two using a temp node.

Question 32

Iterative inorder traversal

Answer 32

Maintain a stack s and a vector v Push root into s Curr=root-left Now go left left left left left. Then print and go one step right and again left left left left and repeat ``` While (s not empty or curr) While (curr) S.push(curr) Curr= curr-> left Node* temp= s.top() V.push_back temp S.pop() Curr=curr-> right ```

Question 33

Iterative preorder traversal

Answer 33

Similar to level order traversal except that we use a stack and enqueue children in reverse order ``` S.push(root) While s not empty Node* temp =s top V.push_back temp->Val S.pop() If(temp->right) S push(temp-> right) If temp- >left Push left child ```

Question 34

Iterative postorder traversal

Answer 34

Left left left left left then right and again left left left left and then root ``` While( s not empty or curr not null) If curr is not null Then s.push curr->left Curr=curr-> left Else Node* temp= s.top()->right If temp- is null then we have processed the right part completely Then temp= s.top() S pop() V.puah_back(temp-val) While stack is not empty and temp arrow right exists {Temp is s.top() s.pop() V.push_back(temp-val) } Else Curr=temp ```

Question 35

BST iterator

Answer 35

We are going to use a stack. Left node and right Go to extreme left nd put everything into the stack. Whenever next is called you take out top of stack and if it has a right child, you go right and again go left and put everything on the way to stack

Question 36

Cousins of a given node

Answer 36

Same as level order traversal except that we maintain a flag which is set to true. If we are at the parent of the given node then we set the flag to false, and when the flag is set, we do not push its children So we will not be pushing the given node nor its sibling. While q not empty V push"back(q.front()) Q.pop()

Question 37

Reverse level order traversal

Answer 37

Same as order traversal except that we store each level in a vector and push that vector into a stack and clear the vector or queue for the next level

Question 38

Vertical order traversal

Answer 38

Create a map Do level order traversal and put nodes into map ``` Q.push(root,0) While ( q not empty) P= q.front() Curr=p.first HD=p second M[hd].pushback(curr-data) Q.pop() If ( curr-left) Q.push( curr-left, hd-1) Similarly right hd+1 ```

Question 39

Check if bst

Answer 39

Find maximum in left subtree Find minimum in right subtree Check if current node is greater than max and less than minimum Efficient For root range is -infi to +infi In left child of the node in range we change upper bound as the nodes value For right child of the node, we change lower bound as the nodes value

Question 40

Change tree with child sum property

Answer 40

``` If(!root) return If leaf node return Change left sub tree Change right subtree Val is root Val Int left=0 Int right=0 If root-left Left is it Val Similarly right If root-val is less than the sum of left and right just increase roots value to sum If Val greater than sum since we cannot decrease value We increase the Val of children Int rem =val-left-right If root-left Root-left-val+=rem Since w e have now modified left subtree it might not be chdsum. So change left subtree again Change tree of root-left Else Root-right-val+=rem Change tree of root-right ```

Question 41

Maximum sum with non adjecent nodes

Answer 41

Case 1 we consider the root. In that we cannot consider it's children as they are adjecent. We can consider it's grandchildren. Max possible sum with considering the root will then be Root value + maximum possible sum of each of the 4 grandchildren Sum1=root If(root-left) Sum1+=func(root-left-left)+func(root-left-right) If(root-right) Sum1+= func(root-right-left)+ func(root-right-right) ``` Case 2 when we don't consider root. Then we can consider it's children Sum2=func(root-left)+func(root-right) Ans=max(ans, max(sum1,sum2)) Return max(sum1,sum2) ``` We use dp to optimise Memoization Map of nodes and int

Question 42

Delete node in bst

Answer 42

``` If(!root) return Null If leaf node and Val is key return null else return root If root-val is key Then we will be deleting node If no right child then return left child If no left child then return right child Else Add left child to the left most node of the right subtree and return right subtree Left_tree is root-left Right_tree is root-right Curr = root-right While(curr and curr-left) Cur=cur-left Curr-left= left_tree Return right_tree Else Root-left=delnode(root-left, key) Root-right=delnode(root-right,key) Return root ```

Question 43

Trim BST trim the given tree so that all elements lie between low and high, without changing the realtive structure of the elements that will remain in the tree.

Answer 43

If not root return null If leaf node and is in range return root, else null If root Val is greater than upper bound, then whole of right subtree will also be greater, so return trimBST(root-left) If root value is lower than lower bound, while left subtree will also be lower. So return trimBST of root-right Else if root is in range, then check for left and right subtrees Root-left is trimBST (root-left) Root-right is trimBST (root-right) Return root

Question 44

Predecessor and successor | Find the inorder predecessor and successor of the given key in bst

Answer 44

``` If root ret null Findpresuc(root-left) If (rootkey && such=null) Suc=root Findpresuc(root-right) ```

Question 45

Convert BST to greater tree

Answer 45

``` Global variable suffix sum Treeanode* convert( root) If !root return null Root-right=convert(root-right) Root-val+=suffix sum Suffix sum=root Root-left=convert(root-left) Return root ```

Question 46

Binary tree pruning | Given the root of a binary tree return the same tree where every subtree not containing one has been removed

Answer 46

``` Bool check(root) This function is used to check if a given tree has 1 If ! root return null If root Val is 1 return true If check(root-left) is true then return true If check(root-left ) is true then return true Return false ``` ``` Prune(root) If(!root) return null Root-left=prune(root-left) Root-right=prune(root-right) If(!check(root-left)) root-left is null If(!check(root-right)) root-right is null If leaf and Val 0 return null Return root ```

Question 47

Insert into bst

Answer 47

``` We are going to always insert at the bottom Insert(root,key) If key>root we move right If root-right root-right=Insert(root-right,key) Else Root-right = new node ``` ``` If key less then root we move left If (root-left) Root-left=insert(root-left, key) Else Root-left is new node ```

Question 48

Most frequent subtree sum. If there is a tie return all values with highest frequency in any order

Answer 48

``` Int findsum(root, dp, m) If !root return 0 If dp(root) m(dp(root))++ ret dp(root) Else Dp(root)=root-val+ findsum(root-left)+findsum(root-right) m(dp(root))++ Return dp(root) ``` In the main function call findsum Now iterate through map and find the max Freq Again iterate through the map and for all sums with max Freq insert into and and return ans

Question 49

Path sum 3 Given a root of a binary tree , return the number of paths which sum to target sum Paths need not necessarily start at root or end at leaf nodes. They can only be downwards

Answer 49

``` The idea is to find the number of paths which start with root We do this using dfs func Then Findpaths(root, targetsum) If not of root return 0 Int ans=0 Count=0 Ans+=DFS(root, target sum) Count=0 Ans+= pathsum(root-left,targetsum) Count=0 Ans+=pathsum(root-right,targetsum) Return ans ``` ``` Global variable count DFS(root, Val, sum) If not root return 0 Sum+=root-val If sum is target count++ DFS(root-right, target,sum) Similarly left Return count ```

Question 50

Add one row to tree

Answer 50

``` Level order traversal If level is depth -1 then Save left and right trees Add new nodes Temp-left-left=left_tree Temp-right-right=right tree ``` Hande the case when level is 1 seperately

Question 51

Flip bt to match preorder traversal

Answer 51

We do preorder traversal and keep track of of prev node. Here prev node means parent. If root doesn't match with pre[preindex] then we probably have to swap the children of prev But there are several corner case to consider. If previously we found not possible then just return not possible If prev is null then its the case when first element itself doesn't match. So not possible If prev exists but has no left or right child then also not possible If prev exists and pre[preindex] is prev-right then only we should swap the children. Else not possible. When we swap, we need to update root to its new node. Very important

Question 52

Insert into max tree

Answer 52

First of all if root is null, then we will have to create a node with given Val and return that node There can be 2 cases. If Val is greater than root, then it would have been the first element to be picked up. And since it is appended to prev array, prev tree will be on its left. So if Val is greater than root, just add root to left of new node Else It will be inserted somewhere in the right tree only as it is appended at last. So root-right is insertintomaxtree(root-right,Val) Return root It will either be greater than some node in the right tree or rightmost, in which case it will fall into null category

Question 53

Flip equivalent binary trees

Answer 53

``` If !root1 and !root2 true Else if not of one then false If we are given root nodes and their Val are same then true If roots do not match false Else If lt1 and lt2 are eqv and rt1 and rt2 are eqv Or lt1 and rt2 are eqv and rt1 and lt2 Are eqv then true Else false ```

Question 54

Sorted array to bst

Answer 54

We need to maintain start index and end index of the given array. Note that root will be the mid element. For this we have count=ei-si+1 Mid is count/2 Val=arr(si+mid) Root-left=func(arr, si, si+mid-1) Root-right=func(arr, si+mid+1,ei) Return root

Question 55

Count number of nodes in

Answer 55

Find ht of left subtree and right subtree. If they are equal then, h+1 2power h-1 Else if they are not equal recursively call on left and right subtrees

Question 56

Maximum path sum between 2 leaves

Answer 56

``` Idea is to use a function which returns maximum root to leaf sum in a given tree If !root ret -1 If leaf then return it's Val Left =func(root-left,ans) Righ=func(root-right,and) Ans=max(ans, left +right+root) Return max(left+root, right+root) ```

Question 57

Preorder inorder and postorder in single traversal

Answer 57

The idea here is that for prerder traversal we print the node on its first visit itself, while for inorder we print a node on its second visit ad postorder on its 3 visit So we maintain a stack and push {Val,num} where num is either 1 2 or 3 We also create 3 seperate lists for in,pre and post. Initially we push root While stack is not empty. We pop and If num is 1 then print into preorder and, and push left child Similarly if 2 push right child If 3 none

Question 58

Height of binary tree from inorder and preorder

Answer 58

Level order taversals of left and right subtrees are not consecutive. We have to hand pick them to make new level orders for left and right ``` Get index of current root in inorder traversal. Count elements in left subtree. Ri-st Count elements on right subtree End-ri Declare two arrays left and right Extract values from level order traversal array For i from 0to n J from st to ri-1 If level(i)==in(j) Left.push_back(level(i)) Similarly for right level order, with j from ri+1 to end ``` Now recursively call on left and right subtrees

Question 59

Lca in bst

Answer 59

If Val EQ to x or y return root If root Val is greater than min of x,y and less than max of x,y return root Lca1 and lca2 If root value is greater than both return lca 1 Else if less than both return lca2 Else null

Question 60

Populate next right pointers

Answer 60

We do this in two steps First for every root we connect next of left child to its right child Second We again traverse and if root has a next We connect root-right -next to root-next-left Return root2 Simple! We can also do level order traversal and connect temp-next to q.front() if i is not equal to count-1

Question 61

Distribute coins in a binary tree

Answer 61

``` Int func(root) If root is null return 0 Int l=func(root-left) Int r=func(root-right) Steps+=abs(l)+abs(r) Return l+r+root-val-1 ```

Question 62

Subtree of another tree

Answer 62

``` Function to check if two trees are identical Bool isSubtree(root, subroto) If both are null return true Else if only root is null return false Else if subroot is null return true Else If values match and they are the same tree return true Else return subtree(root-left,subroot) or subtree(root-right,subroot) ```