Tempo Flashcards
Degree of a node is the number of children it has. Degre is 0 then leaf otherwise intermediate node
Level order traversal
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
Level order traversal line by line
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.
Size of bt
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
Maximum in bt
If root is null return int-min. Else max is the maximum of root, maximum of left subtree nd maximum of right subtree
Height of bt
If root is null return 0..
Else ht is Max of left and right ht +1
Print nodes at distance k
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
Left view
Level order traversal
At each level only when I=0 print else proceed same as level order traversal
Childsum
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
Height balanced tree
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
Convert bt to dll
Inorder traversal, inplace
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
By from inorder and preorder traversal
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
Spiral order traversal
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
Diameter of binary tree
The number of nodes present in the longest path present between two leaf nodes
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
Lca
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
Serialisation
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
Deserialisation
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
Kth smallest number
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)
2 sum bt
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
Recover BST
Two elements of a BST are swapped by mistake. Correct them to recover bst
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.
Sum of root to leaf nodes
Each root to leaf path can represent a number. Return the sum of all such numbers
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)
Path sum
Given a BST and a sum, determine if there is a path with given sum
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.
Minimum depth of a bt
Void DFS(root, count) If not root return If leaf node then and is Max( ans, count) Count++ DFS(root+> left, count) Similarly right
Path to given node
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
