void LevelOrder(struct BinaryTreeNode *root), struct BinaryTreeNode *temp; struct Queue *Q = CreateQueue(); iflroot) return; EnQueue|Q,root}; while{IsEmptyQueue(Q)) { temp = DeQueuelQ); / /Process current node print{(‘Mod”, temp—data); ifltemp—left} EnQueue(Q, templefi); ifftemp—right) EnQueue(Q, temp-right); | DeleteQueue(Q); ! Time Complexity: O(n). Space Complexity: O(n). Since, in the worst case, all the nodes on the entire last level could be inthe queue simultaneously. Binary Trees: Problems & Solutions Problen-1 Give an algorithm for finding maximum element in binary tree, Solution: One simple way of solving this problem is: find the maximum element in left subtree, find the maximum element in right sub tree, compare them with root data and select the one which is giving the maximum value. This approach can be easily implemented with recursion.Time Complexity: O(n). Space Complexity: O(n). Problen-2 Give an algorithm for finding the maximum element in binary tree without recursion. Solution: Using level order traversal: just observe the element’s data while deleting,int FindMaxUsingLevelOrder(struct BinaryTreeNode *root){ struct BinaryTreellode *temp; {nt max * INT_MIN; struct Queue *Q = CreateQueuel); EnQueue(Q,root); ‘while({IsEmptyQueue(Q) | temp = DeQueue(Q); || \argest of the three values iflmax < tempdata} max = temp-data; iftemp left) EnQueue (Q, templet) ifftemp-right} EnQueue (Q, temp--right); } DeleteQueue(Q); retum max; | ‘Time Complexity: O(n), Space Complexity: O(n). Problenr3 Give analgorithm for searching an element in binary tree. Solution: Given a binary tree, return true if a node with data is found in the tee. Recurse down the tree, choose the left or right branch by comparing data with each noce’s data,int FindInBinaryTreeUsingRecursion|struct BinaryTreeNode *root, int data) { int temp; | | Base case == empty tree, in that case, the data is not found go return false iffroot == NULL) return 0; else | | [see if found here iffdata == rootdata) return 1} else { || otherwise recur down the correct subtree temp = FindlnBinaryTreeUsingRecursion (root-sleft, data) ifftemp |= 0) Tetum temp; else return (PindInBinarylreeUsingRecursion (root-ight, data); ) J ) return 0; } ‘Time Complexity: O(n), Space Complexity: O(n). Problem-4 Give analgorithm for searching an element in binary tree without recursion. Solution: We can use level order traversal for solving this problem, The only change required in level order traversal is, instead of printing the data, we just need to check whether the root data is equal to the element we want to search,int SearchUsingLevelOrder(struct BinaryTreeNode ‘root, int data}{ struct BinaryTreeNode *temp; struct Queue *Q; if{troot} return -]; Q= CreateQueue() EnQueue(Q,toot); while(IsEmaptyQueve(Q) { temp = DeQueue(Q); [ {see if found here ifldata == root—data) return 1; ifltemp—left) EnQueue (Q, temp~lett); iftemp-right) EnQueue (Q, temp-sright); 1 DeleieQuene( 0) retum 0; i ‘Time Complexity: O(n), Space Complexity: O(”). Problem-5 Give an algorithm for inserting an element into binary tree. Solution: Since the given tree is a binary tree, we can insert the element wherever we want. To insert an element, we can use the level order traversal and insert the element wherever we find the node whose left or right child is NULL.void InsertlnBinaryTree(struct BinaryTreeNode *root, int datall struct Queue *Q; struct BinaryTreeNode *temp; struct BinaryTreeNode *newNode; newNode = (struct BinaryTreeNode *) malloc(sizeof{struct BinaryTreeNode)|; newllode—left = newNode-right = NULL; iffinewNode} { printfl’Memory Error”) return; } iroot | root = newNode; retum; } Q= CreateQueuel); EnQueue(Q,root]; while(lisEmptyQueue(Q)) { temp * DeQueue(Q}, ifltemp-left) EnQueue(Q, temp—left); else { temp—left-=newNode; DeleteQuevelQ); return; J ifltemp-right} EnOuevel0, temp-right!: else | temp—rightsnewNode; DeleteQueuelQ); return; | | DeleteQueue(Q); }‘Time Complexity: O(n). Space Complexity: O(n). Problem-6 Give analgorithm for finding the size of binary tree. Solution: Calculate the size of left anc right subtrees recursively, add 1 (current node) and return to its parent, |/ Compute the number of nodes in a tree. int SizeOfBinaryTree(struct BinaryTreeNode *root} { iflroot==NULL) return 0; else return(SizeOBinaryTree(root—left) + | + SizeOfBinaryTree{root—right)}, } J ‘Time Complexity: O(n), Space Complexity: O(n). Problem-7 Can we solv» Problem-6 without recursion? Solution: Yes, using level order traversal. int SizeofBTUsingLevel Order{struct BinaryTreeNode ‘root}{ struct BinaryTreellode *temp; struct Queue *Q; int count = 0; ifflroot) return 0; Q = CreateQueue(|; EnQueue(Q,root); while(!IsEmptyQueve(Q)) { temp = DeQueue(Q}; count! +; iffemp-lett EnQueue (Q, temp~lett); ifltempright) EnQueue (Q, temp-right); } DeleteQueue(Q); return count;‘Time Complexity: O(n). Space Complexi Problem-8 Give an algorithm for printing the level order data in reverse order. For example, the output for the below tree should be: 4.567231 root (:) void LevelOrderTraversallnReverse(struct BinaryTreeNode *root}) struct Queue ‘0; struct Stack *s = CreateStack(); struct BinaryTreeNode *temp; ifltroot} return; Q = CreateQueue(}; EnQueue(Q, root}; while(lIsEmptyQueue(Q)) { temp = DeQueue(()); ifltemp—right) EnQueue(Q, temp-right); if{temp—left) EnQueue (Q, temp—left}; Push(s, temp); Solution: } vhile(![sEmptyStack(s)) printi(“%d" Pop(s)-sdatal;‘Time Complexity: O(n). Space Complexity: O(n). Problem-9 Give an algorithm for deleting the tree. Solution: root () ‘To delete a tree, we must traverse all the nodes of the tree and delete them one by one. So which traversal should we use: Inorder, Preorder, Postorcler or Level order Traversal? Before deleting the parent node we should delete its children nodes first. We can use postorder traversal as it does the we without storing anything, We can delete tree with other traversals also with extra space complexity. For the following, tree nodes are deleted in order —4,5,2,3,1. void DeleteBinaryTree(struct BinaryTreeNode *root){ iflroot == NULL) return; /* first delete both subtrees */ DeleteBinaryTree(root let) DeleteBinaryTree|root—right); //Delete current node only after deleting subtrees free(toot|; | ‘Time Complexity: O(n), Space Complexity: O(n). Problem-10 Give an algorithm for fircling the height (or depth) of the binary tree. Solution: Recursively calculate height of left and right subtrees of a nocle ancl assign height to the node as max of the heights of two children plus 1. This is similar to PreOrder tree traversal (and DFS of Graph algorithms).int HeightOfBinaryTree(struct BinaryTreeNode ‘root){ int leftheight, rightheight; iflroot == NULL) return 0; else | /* compute the depth ofeach subtree */ leftheight = HeightOfBinaryTree|root—left}; tightheight = HeightOfBinaryTree(root-right); iflletheight > rightheight) return(leftheight + 1); else return(rightheight + 1); } ) ‘Time Complexity: O(n), Space Complexity: O(n). Problem-11 Can we solv» Problem-10 without recursion? Solution: Yes, using level order traversal. This is similar to BFS of Graph algorithms, End of level is identified with NULL.‘Time Complexity: O(n), Space Complexity: O(7), Problem-12 Give analgorithm for finding the deepest node of the binary tree. Solution:struct BinaryTreeNode *DeepestNodeinBinaryTree(struct BinaryTreeNode *roat){ struct BinaryTreeNode *temp; struct Queue *Q; ifllroot} return NULL; Q = CreateQueue() EnQueue((),root); while(![sEmptyQueue(Q)) | temp = DeQueve(0) ifempleft} EaQueue(Q, temp—lefi); ifltemp-right) EnQueue(Q, temp-right); | DeleteQueue(Q); retum temp; | Time Complexity: O(n), Space Complexity: O(n). Problem-13 Give an algorithm for deleting an element (assuming data is given) from binary tree. Solution: The deletion of a node in binary wee can be implemented as Starting at root, find the node which we want to clelete, Find the deepest node in the tree. Replace the deepest node’s data with node to be deleted, Then delete the deepest node. Problem-14 Give an algorithm for finding the number of leaves in the binary tree without using recursion. Solution: The set of nodes whose both left anc right children are NULL are called leaf nodes.int NumberOfLeaveslnbTusingLevelOrder(struct BinaryTreeNode *root){ struct BinaryTreellode *temp; struct Queue *Q; int count = 0; ifftroot) return 0; Q = CreateQueue(|; EnQueue(Q,root); while(!IsEmptyQueue() { temp = DeQueve(Q}: if(ttemp-rleft && Itemp—right) countt+; else{ ifitemp-left) EnQueue(Q, templett); ifltemp—right) EnQueue(Q, temp—right); } | DeleteQueue(Q); return count; | ‘Time Complexity: O(n). Space Complexi Problem-15 Give analgorithm for finding the number of full nodes in the binary tree without using recursion. Solution: The set of all nodes with both left and right children are called full nodes,int NumberOfullNodeslnBTusingLevelOrder(struct BinaryTreeNode *root}{ struct BinaryTreellode *temp; struct Queue *Q; int count = 0; iffroot) return 0; Q= CreateQueuie(); EnQueue(Q,root}; while({IsEmptyQueue(Q)) { temp = DeQueue(Q}: ifltemp—left && temp-right) count++; ifltemp—left) EnQueue (Q, templet}; if{temp-right) EnQueue (0, temp-sright}; | DeleteQueue(Q); retum count; } ‘Time Complexity: O(n). Space Complexity: O(n). Problem-16 Give an algorithm for finding the number of half nodes (nodes with only one child) in the binary tree without using recursion, Solution: The set of all nodes with either left or right child (but not both) are called half nodes.int NumberOfHaliNodesInBTusingLevelOrder{struct BinaryTreeNode *root}{ struct BinaryTreeNlode ‘temp; struct Queue *Q; int count = 0; iflroot) retum 0; Q = CreateQueue(}; EnQueue((,root}; while(IsEmptyQueue(Q)) { temp = DeQueue(Q); | /sve can use this condition also instead of two temp-left * temp-right iflltempleft && tempright || temp—left && ltemp—right| count++; ifltemp-lett) EnQueue (Q, templeit}; ifltemp-right) EnQueve (Q, temp-right); | DeleteQueue(Q); return count; } ‘Time Complexity: O(n). Space Complexity: O(n). Problenr17 Given two binary trees, return true if they are structurally identical. Solution: Algorithm: + If both trees are NULL then return tue, + If both trees are not NULL, then compare data and recursively check left and right subtree structures.| /Return true if they are structurally identical, int AreSiructurullySame'Trees(struct BinaryTreellode *rootl, struct BinaryTreeNode *root2) { [both empty1 ifroct|==NULL && root2==NULL) retumn 1; iroct]==NULL | | root2==NULL) return 0; || both non-emptycompare them retumiroot]—data == root2—data fd: AreStructurullySameTrees(rootl—lefi, root2—letf) && AreStructurllySameTrees(rootl right, oot2-sright); ! ‘Time Complexity: O(n). Space Complexity: O(n), for recursive stack. Problem-18 Give an algorithm for finding the diameter of the binary tree. The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. Solution: To find the diameter of a tree, first calculate the diameter of left subtree and right subtrees recursively, Among these two values, we need to send maximum value along with canrent level (+1).int DiameterOfTree(struct BinaryTreeNode *root, int *ptri{ int left, right; ifflroot) retum 0; left = DiameterOfTree(root—left, ptr), right = DiameterOTree(root-sright, ptr} iflleft + right > *ptz) ptr = left + right, return Max(left, right)+1; } | [Alternative Coding static int diameter(struct BinaryTreeNodle *root) { if (root == NULL} return 0; int [Height = height(root->eft}; int rHeight = height{rcot-right); int Diameter » diameter(root-left) int rDiameter = diameter(root-right), retum max(lHeight + Height + 1, max([Diameter, rDiameter)); | |* The function Compute the "height" ofa tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ static int height(Node root} { if (root == null) return 0; retum 1 + max{height{root left), height(root right); } ‘There is another solution and the complexity is O(n). The main idea of this approach is that the node stores its left child’s and right chilel’s maximum diameter if the nocle’s child is the “root”, therefore, there is no need to recursively call the height method. The drawback is we need to add ‘two extra variables in the node structure.int findMaxLen(Node root] | int nMaxLen = 0; if (root == null) retum 0; if (root left == null) root.aMaxLeit = 0; if (oot.right == null) root.aMaxRight = 0; if root let |= null) findMaxLen (root left; if (rootright = null} findMaxLen|root.right); if (root left != null) | int nTempMaxLen = 0; nlempMaxLen = {root.left.nMaxLeft > root.left.nMaxRight} ? root left.nMaxLeft: root left. nMaxRight; root.nMaxLeft = nTempMaxLen + 1; } if (root.right != null) { int nTempMaxlen = 0; nTempMaxLen = {root.right nMaxLeft > root.right.nMaxRight) ? foot.right nMaxLeft : root.right. nMaxRight, root. nMaxRight = nTempMaxLen + 1; \ } if (rootnMaxLelt + root.nMaxRight > nMaxLen} MaxLen = rootnMaxLeft + root.nMaxRight; retum nMaxLen; i ‘Time Complexity: O(n), Space Complexity: O(M). Problem-19 Give an algorithm for finding the level that has the maximum sum in the binary tree. Solution: The logic is very much similar to finding the number of levels. The only change is, weneed to keep track of the sums as well,int FindLevelwithMaxSum(struct BinaryTreeNode *roat){ struct BinaryTreeNlode ‘temp; int level=0, maxLevel=0; struct Queue *Q; int currentSum = 0, maxSum = 0; ifltroot} return 0; Q=CreateQueuel); EnQueue(Q,root}; EnQueue(Q, NULL}: [/End of first level. while(IsEmptyQueve(Q)) | temp “DeQueuc(Q), [/ the current level is completed then compare sums ifltemp == NULL) { iffeurrentSum> maxSum) | maxSum = currentSum; maxLevel = level; } currentSum = 0; | [place the indicator for end of next level at the end of queue iffllsEmptyQueue()) EnQueue(Q,. NULL); level}+; else | currentSum += temp—data; ifltemp—lefi) EnQueue(temp, temp—left); iffrootright) EnQueue(temp, temp-right), \ \ i retum maxLevel;‘Time Complexity: O(n). Space Complexity: O(n). Problem-20 — Givena binar Solution: Refer to comments in functions. ree, print out all its root-to-leaf paths, void PrintPathsRecur(struct BinaryTreeNode *roct, int path), int pathLen) { iffteot ==NULL) retum; || append this node to the path array path[pathLen] * rootdata; pathLen#+; || it's a leaf, so print the path that led to here iffroot—left==NULL && root-right==NULL) PrintArray(path, pathLen); elie | | /othenvise try both subtrees PrintPathsRecur{rootleft, path, pathLen); PrintPathsRecur{root-right, path, pathLen), } ) } | / Function that prints out an array on a line, void PrintArray(int ints), int len) { for lint i=0; islen; i++) printfi“%d” intsi}; } ‘Time Complexity: O(n). Space Complexity: O(n), for recursive stack. Problem-21 Give an algorithm for checking the existence of path with given sum. That means, given a sum, check whether there exists a path from root to any of the nodes. Solution: For this problem, the strategy is: subtract the node value from the sum before calling its children recursively, and check to see if the sun is 0 when we Tun out of tree,void PrintPathsRecur(struct BinaryTreeNode *root, int path}, int pathLen) { iffroot ==NULL) retum; /| append this node to the path array path[pathLen] = root—data; pathLen+; | it's a leaf, so print the path that led to here ifftoot—left==NULL && root—right»"NULL) PrintArray(path, pathLen); else | || othenvise try both subtrees PrintPathsRecur{rootleft, path, pathLen); PrintPathsRecur{root-right, path, pathLen|; } } | | / Function that prints out an array on a line, void PrintArray(int ints[), int len) | for fint i=0; islen; i++) printf*%d” intsiilj; ilfrootleft && root—right)| |(troot-left fits troot—right}) return(HasPathSum(root—left, remainingSum) | | HasPathSum(rootright, remainingSum)); else iffroot->left) return HasPathSum(root—eft, remainingSum); else return HasPathSum|root-right, remainingSum); } ‘Time Complexity: O(n), Space Complexity: O(”). Problem-22 Give an algorithm for finding the sum of all elements in binary tree, Solution: Recursively, call left subtree sum, right subtree sum and add their values to current nodes data,int Add(struct BinaryTreeNode *toot] { iffrcot == NULL) Tetum 0; else return (rootdata + Add{rootlefi) + Add{root—right)}; i ‘Time Complexity: O(n), Space Complexity: O(n). Problem-23 Can we solv» Problem-22 without recursion? Solution: We can use level order traversal with simple change. Every time after deleting an element from queue, add the nodes data value to sum variable. int SumofBTusingLevelOrder(struct BinaryTreeNode *toat}| struct BinaryTreellode *temp; struct Queue *Q; int sum =0; ifflroot) retum 0; Q = CreateQueue(}; EnQueue(Q,toot}; while(![sEmptyQueue(Q)) | temp = DeQueue(Q); sum += temp—data; ifltempleft) EnQueue (Q, templeit); ifltemp-right} EnQueue (Q, temp—right); J DeleteQueue(Q); retum sum; 1 1 ‘Time Complexity: O(n), Space Complexity: O(”). Problen-24 Give an algorithm for converting a tree to its mirror. Mirror of a tree is another tree with left and right children of all non-leaf nocles interchanged. The trees below are minrors to each other,root () root CG) Solution: struct BinaryTreeNode *MirrorOfBinaryTree(struct BinaryTreeNode *root}{ struct BinaryTreellode * temp; iffroot) { MirrorOfBinaryTree{rootlefi}; MitrorOfBinaryTree(rootright}; /* swap the pointers in this node */ temp = rootleft; tootlelt = rootright; root-sright = temp; | retuzm root; | Time Complexity: O(n), Space Complexity: O(n). Problem-25 Given two trees, give an algorithm for checking whether they are mirrors of each other. Solution:int AreMirrors(struct BinaryTreeNode * root], struct BinaryTreeNode * rootQ] { iffroot] == NULL && mot2 == NULL) return 1; iffroot] == NULL | | root == NULL) return 0; ifftoot] data != root2—data) return 0; else return AteMirrors(root]—left, root2—-right) && AreMirrors{toot right, root2left}; | ‘Time Complexity: O(n). Space Complexity: O(n). Problem26 Give analgorithm for finding LCA (Least Common Ancestor) of two nodes ina Binary Tree, Solution: struct BinaryTreeNode *LCA(struct BinaryTreeNode ‘root, struct BinaryTreeNode *a, struct BinaryTreeNode *B)( struct BinaryTreellode “left, right; iffroct == NULL) teturn root; iffroat == a || root == p) return root; left = LCA (root—left, a, B); right= LCA {root-right, a, 6 iffleft && nght) return root; else return (left? left: right) ‘Time Complexity: O(n), Space Complexity: O(n) for recursion, Problem27 Give an algorithm for constructing binary tree from given Inorder and Preorder taversals. Solution: Let us consider the traversals below: Tnorder sequence: D BE AFC Preorder sequence: ABD ECFIna Preorder sequence, leftmost element denotes the root of the tree. So we know ‘A’ is the root for given sequences, By searching ‘A’ in Inorcer sequence we can find out all elements on the left sicle of £4’, which come under the left subtree, and elements on the right side of ‘4’, which come under the right subtree. So we get the structure as seen below. \We recursively follow the above steps antl get the following tree, root (a) Algorithm: BuildTree() 1 RUN 6 Select an element from Preorder, Increment a Preorder index variable (preOrderIndex in code below) to pick next element in next recursive call. Create a new tree nocle (newNode) from heap with the data as selected element. Find the selectecl element’s index in Inorder. Let the index be inOrderIndex. Call BuildBinaryTree for elements before inOrder Index anc make the built tree as left subtree of newNode. Call BuildBinaryTree for elements after inOrderIndex and make the built tree as right subtree of newNode. return newNode.struct BinaryTreeNode *BuildBinaryTree(int inOrder]}, int preOrder(), int inOrderStar, int inOrlerEnd)y static int preOrderlndex = 0; struct BinaryTreeNode *newNode; iffinOrderStart > inOrderEnd) etum NULL; newNode = (struct BinaryTrecNode *) malloc (sizeof{struct BinaryTreeNode}); iflinewNode} | prnt{(*‘Memory Error’); return NULL // Select current node from Preorder traversal using preOrderIndex newNode-data = preOrderipreOrderindex), preOrderlndex++; iffinOrderStart == inOrderEnd) return newNode; / | find the index of this node in Inorder traversal int mOrderlndex = Search(inOrder, inOrderStari, inOrderEnd, newNodedata), / /Fill the left and right subtrees using index in Inorder traversal newNode-left = BuildBinaryTree(inOrder, preOrder, inOrderStart, nOrderindex -1); newNode—right = BuildBinaryTree(inOrder, preOrder, inOrderlndex +1, inOrderEnd); return newNode; | ‘Time Complexity: O(n), Space Complexity: O(M). Problem-28 If we are given two traversal sequences, can we construct the binary tree uniquely? Solution: It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed uniquely, otherwise not. ‘Therefore, the following combinations can uniquely identify a tree: + Inorder and Preorder + Inorder and Postorder . Tnorder and Level-order‘The following combinations do not uniquely identify a tree, + Postorder and Preorer + Preorder and Level-order + Postorder and Level-order For example, Preorder, Level-order and Postorder traversals are the same for the above trees: So, even if three of them (PreOrder, Level«Order and PostOrder) are given, the tree cannot be constructed uniquely. Problem-29 Give an algorithm for printing all the ancestors of a node in a Binary tree. For the tree below, for 7 the ancestors are 1.3 7. root Solution: Apart from the Depth First Search of this tree, we can use the following recursive way to print the ancestors.int PrintAllAncestors(struct BinaryTreeNode ‘toot, struct BinaryTreeNode *node}{ iffreot == NULL return 0; iffrootleft == node || root-—right == node || PrintAllAncestors(toot—left, node) || PrintAllAncestors(root—right, nodel} | printf"id"root-data); return 1; ) 4} return 0; | ‘Time Complexity: O(n). Space Complexity: O(n) for recursion. Problen-30 Zigzag Tree Traversal: Give an algorithm to traverse a binary tree in Zigzag order, For example, the output for the tree below should be: 1.324567 root (:) (2) : Solution: This problem can be solved easily using two stacks, Assume the two stacks are: currentLevel and nextLevel. We would also need a variable to keep track of the current level order (whether itis left to right or right to left). ‘We pop from currentLevel stack and print the node’s value. Whenever the current level order is from left to right, push the node’s left child, then its right child, to stack nextLevel. Since a stack is a Last In First Out (LIFO) structure, the next time that nodes are popped off nextLevel, it will be in the reverse order. On the other hancl when the current level order is from right to left, we would push the nocle’s right child first, then its left child. Finally, don’t forget to swap those two stacks at the endl of each level (i. e., when currentLevel is empty).void ZigZagTraversal {struct BinaryTreeNode *root}{ struct BinaryTreellode *temp, int leftToRight = 1; ifliroot) Tetum; struct Stack *currentLevel = CreateStack(), ‘nextLevel = CreateStack!); Push(currentLevel, root}; while(!IsEmptyStack{currentLevell) { temp = Pop(currentLevel}; ifftemp) { print{l“%od” temp—data); iffletToRight) { ifftempleft) Push(nexiLevel, temp-left}, iftemp-right) Push(nextLevel, temp=right), \ 1 else{ _ ifftemp-right] Push(nextLevel, temp—right}; ifftemp—left) Push{nextLevel, temp—lett); } ifllsEmptyStack(currentLevel) | leftToRight = I-letToRight; swap(currentLevel, nextLevel); } ‘Time Complexity: O(n). Space Complexity: Space for two stacks = (7) + O(n) = O(n). Problem-31 Give an algorithm for finding the vertical sum of a binary tree, For example, The tree has 5 vertical lines Vertical-1: nodes. Vertical-2: nodes: Vertical vertical sum is 4 vertical sumis 2 > vertical sumis 1 +5 +6 = 12 Vertical-4: nod vertical sum is 3 Vertical-5: noces-7 => vertical sum is 7 ‘We need to output: 421237root (:) Solution: We can do an inorder traversal and hash the column, We call ‘VerticalSuminBinaryTreefroot, 0) which means the root is at colurm 0. While doing the traversal, hash the column and increase its Value by root — data. void VerticalSumInBinaryTree (struct BinaryTreeNode *root, int column); iflroot==NULL) return; VerticalSuminBinaryTree(toot—left, column-l), | /Refer Hashing chapter for implementation of hash table Hash{column| += root-rdata; VerticalSumInBinaryTree(rootright, column* |); 1 } VerticalSumInBinaryTree|root, 0); Print Hash; Problen+32 How many different binary trees are possible with n nodes? Solution: For example, consider a tee with 3 nodes (n = 3), It will have the maximum combination of 5 different (i.e, 2° =3 = 5) trees. wo?In general, if there are n nodes, there exist 2" -n different trees. Problem-33 Given tree with a special property where leaves are represented with ‘I? and internal node with ‘I’, Also, assume that each node has either 0 or 2 children. Given preorder traversal of this tree, construct the tree. Example: Given preorler string => [ILL root Solution: First, we should see how preorder traversal is arranged. Pre-order traversal means first put root node, then pre-order traversal of left subtree and then pre-order traversal of right subtree. In a normal scenario, it’s not possible to detect where left subtree ends ancl right subtree starts using only pre-order traversal, Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists. So every time when we are computing a subtree, we need to compute its sibling subtree as well. Secondly, whenever we get ‘L’ in the input string, that is a leaf and we can stop for a particular subtree at that point, After this ‘L’ node (left child of its parent ‘1.’), its sibling starts. If 1 node is right child of its parent, then we neec| to go up in the hierarclry to find the next subtree to compute. Keeping the above invariant in mind, we can easily determine when a subtree ends and the next one starts. It means that we can give any start node to our method and it can easily complete the subtree it generates going outside of its nodes. We just need to take care of passing the correct start nodes to different sub-trees.struct BinaryTreeNode *BuildTreeromPreOrder(char* A, int *y)/ struct BinaryTreeNode *newNode; newNode = (struct BinaryTreeNode *) malloo(sizeof{struct BinaryTreeNodel); newNode-data = Aji}; newllodeleft = newNode-right = NULL; iA == NULL), { [Boundary Condition free(newNode}; return NULL; ) Atti} == 1) //On reaching leaf node, return return newNode; ate |; { [Populate left sub tree newNode-left = BuildTreeFromPreOrcer(A, i); eel: | [Populate right sub tree newNode-right = BuildTreeFromPreOrder(A, i); retum newNode; } Time Complexity: O(n). Problem-34 Given a binary tree with three pointers (eff, right and nextSibling), give an algorithm for filling the nextSibling pointers assuming they are NULL initially. Solution: We can use simple queue (similar to the solution 0° Problem-11), Let us assume that the structure of binary tree is:struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; struct BinaryTreellode* nextSibling: \. hb int FillNextSiblings(struct BinaryTreeNode *root)| struct BinaryTreellode *temp; struct Queue "Q; if{lroot) return 0; Q = CreateQueuel}; EnQueue(Q,root); EnQueue(Q,NULL}: while({IsEtaptyQueuelQ)) { temp =DeQueue(Q); // Completion of current level. ifftemp ==NULL) { //Put another marker for next level, ifilsEmptyQueve(Q)) EnQueue((),NULL); else | temp—mnextSibling = QueueFront(Q); iflrootleft) EnQueue(Q, temp—left) if{rootright) EnQueue(Q, temp-right}; 1 | ‘Time Complexity: O(n), Space Complexity: O(n). Problem-35 Is there any other way of solvins Problem-'34? Solution: The trick is to re-use the populated nextSibling pointers, As mentioned| earlier, we justneed one more step for it to work, Before we pass the left and right to the recursion function itself, we connect the right child’s nextSibling to the current node’s nextSibling left child. In order for this to work, the current node nextSibling pointer must be populated, which is true in this case, void FillNextSiblings(struct BinaryTreeNode* root { if ({root) return; if (rootleft] root-sleft-nextSibling = rootright; if (root—right) rootrightnextSibling = (root—nextSibling) ? rootnextSiblingleft : NULL; FillNextSiblings{root—left), FillNextSiblings{rootright), t ‘Time Complexity: O(n). 6.7 Generic Trees (N-ary Trees) In the previous section we discussed binary trees where each node can have a maximum of two children and these are represented easily with two pointers. But suppose if we have a tree with many children at every node and also if we do not know how many children a node can have, how do we represent them? For example, consider the tree shown below.OOD ® & f @ OW) @ & , @) @ © ® How do we represent the tree? In the above tree, there are nodes with 6 children, with 3 children, with 2 children, with 1 child, aml with zero children (leaves). To present this tree we have to consider the worst case (6 children) ancl allocate that many child pointers for each nocle. Based on this, the node representation can be given as: struct TreeNlode! int data; struct TreeNode *firstChild; struct TreeNode *secondChild; struct TreeNode ‘thirdChild; struct TreeNode “fourthChild; struct TreeNode *fifthChild; struct TreeNode *sixthChild hi Since we are not using all the pointers in all the cases, there is a lot of memory wastage. Another problem is that we do not know the number of children for each node in advance, In order to.solve this problem we need a representation that minimizes the wastage and also accepts nodes with any number of children. Representation of Generic Trees Since our objective is to reach all nodes of the tree, a possible solution to this is as follows: + Ateach node Link children of same parent (siblings) from left to right. . Remove the links from parent to all children except the first child. ‘What these above statements say is if we have a link between children then we do not need extra links from parent to all children. This is because we can traverse all the elements by starting at the first child of the parent. So if we have a link between parent and first child and also links between all children of same parent then it solves our problem. This representation is sometimes called first child/next sibling representation. First child/next sibling representation of the generic tee is shown above. The actual representation for this tree is:Element First Child Next Sibling A NULL NULL Based on this discussion, the tree node cleclaration for general tree can be given as: struct TreeNode { int data; struct TreeNode *firstChild; struct TreeNode *nextSibling; Note: Since we are able to convert any generic tree to binary representation; in practice we use binary trees. We can treat all generic trees With a first child/next sibling representation as binary trees. Generic Trees: Problems & Solutions Problem-36 — Givena tree, give an algorithm for fincling the sum of all the elements of the tee. Solution: The solution is similar to what we have done for simple binary trees. That means, traverse the complete list ancl keep on ackdling the values. We can either use level orcler traversalor simple recursion. int FindSum(struct TreeNode *root}} ifilroot) return 0; retum root—data + FindSum|root—firstChild) + FindSum(rootnexiSibling}, Time Complexity: O(n). Space Complexity: O(1) (if we do not consider stack space), otherwise Om. Note: All problems which we have discussed for binary trees are applicable for generic trees also, Insteacl of left andl right pointers we just need to tse firstChild and nextSibling Problem-37 For a 4ary tree (each node can contain maximum of 4 children), what is the maximum possible height with 100 nodes? Assume height of a single node is 0. Solution: In 4-ary tree each node can contain 0 to 4 children, andl to get maximum height, we need to keep only one child for each parent. With 100 nodes, the maximum possible height we can get is 99, If we have a restriction that at least one node has 4 children, then we keep one node with 4 children and the remaining nodes with 1 child. In this case, the maximum possible height is 96. Similarly, with n nodes the maximum possible height is n—4. Problem-38 For a rary tree (each node can contain maximum of 4 children), what is the minimum possible height with n nodes? Solution: Similar to the above discussion, if we want to get minimum height, then we need to fill all nodes with maximum children (in this case 4). Now let’s see the following table, which indicates the maximum number of nodes for a given height. Height, h | Maximum Nodes at height, h = 4" | totat Nodes height oft 1 1 [4 14 2 [4x4 144 x4 3 [4x4x4 Te4 x44 4x44 4 har For a given height h the maximum possible nodes are: ~ To get minimum height, take logarithm on both sides:a4" = 3041 (b+ Dlogd = log3n +1) h+1=logy(3nt1) = h=log,(3n+1)-1 Problem-39 Given a parent array P, where Pfi] intlicates the parent of i" node in the tee (assume parent of root node is indicated with -1). Give an algorithm for finding the height or depth of the tree, Solution: For example: if the P is Its corresponing tree is: From the problem definition, the given array represents the parent array. That means, we need to consider the tree for that array and find the depth of the wee. The clepth of this given tree is 4. If we carefully observe, we just need to start at every node and keep going to its parent until we reach—I ancl also keep track of the maximum depth among all nodes.int FindDepthlnGenerieTtec(int Pl, int n} int maxDepth =-1, current Depth =-1, j; for inti=O;i maxDepth) maxDepth = currentDepth; } retum maxDepth; } Time Complexity: O(7°). For skew trees we will be re-calculating the same values. Space Complexity: OC). Note: We can optimize the code by storing the previous calculated nodes? depth in some hash table or other array. This reduces the time complexity but uses extra space. Problem-40 Given a node in the generic tree, give an algorithm for counting the number of siblings for that node. Solution: Since tree is represented with the first child/next sibling method, the tree structure can be given as: struct TreeNode{ int data; struct TreeNode “firstChild; struct TreeNode *nextSibling; i. i For a given node in the tree, we just need to traverse all its next siblings.int SiblingsCount(struct TreeNade *current){ int count = 0; while(current) { countt+; current = current nextSibling, ) reutm count; | ‘Time Complexity: O(n). Space Complexity: O(1). Problem-41 Given a node in the generic tree, give an algprithm for counting the number of children for that node. Solution: Since the tree is represented as first child/next sibling method, the tree structure can be given as: struct TreeNode} int data; struct TreeNode “firstChild; struct TreeNode ‘nextSibling; h For a given node in the tree, we just need to point to its first child and keep traversing all its next siblings. int ChildCount{struct TreeNode “current int count = 0; current = current—firstChild; while(current) { count; current = current—nextSibling; ) reutm count; | Time Complexity: O(n), Space Complexity: O(1).Problen-42 Given two trees how do we check whether the trees are isomorphic to each other or not? Solution: Two binary trees root and root2 are isomorphic if they have the same structure. The values of the nodes does not affect whether two trees are isomorphic or not. In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tee on the right is isomorphic to the tree on the left, int lslsomorphie(struct TreeNode *rootl, struct TreeNode ‘toot2){ iflrootl 8a !root2) return |; if(rootl 8 root2| || (root &slroot2) return 0; retum (Islsomorphic(root]left, root2—left) && Islsomorphic{rootl right, root2—right)}; } ‘Time Complexity: O(n), Space Complexity: O(n). Problen-43 Given two trees how do we check whether they are quasi-isomorphic to each other or not? Solution:Toot root () a (1) —_ ‘Two trees rootl and root2 are quasi-isomorphic if root] can be transformed into root2 by swapping the left and right children of some of the nodes of rootl. Data in the nodes are not important in determining quasi-isomorphism; only the shape is important. The trees below are quasi-isomorphic because if the children of the nodes on the left are swapped, the tree on the right is obtained. int Quasilsomorphie(struct TreeNode *rootl, struct TreeNode *root2}i ifflrootl 88 {root2 retum 1; ifl({rootl && root2) || (root] && !root2)) retum 0; tetum (Quasilsomorphic(rootl—left, root2—left) && Quasilsomorphic(rootl right, root2-right} | | Quasilsomorphic(root]—right, root2—lefi) && Quasilsomorphic(root!—left, root2right)); } ‘Time Complexity: O(n), Space Complexity: O(n). Problem-44 A fill kary tree is a tree where each node has either 0 or k children, Given an Iv which contains the preorder traversal of full k -ary tree, give an algorithm for constructing the full k -ary tree. Solution: In k -ary tree, for a node at i** position its children will be at k *i + Ltok *i +k. For example, the example below is for full 3-ary tree.(2) © OROTO As we have seen, in preorder traversal first left subtree is processed then followed by root node and right subtree. Because of this, to construct a full k-ary, we just need to keep on creating the nodes without bothering about the previous constructed nodes. We can use this trick to build the tree recursively by using one global index. The cleclaration for k-ary tree can be given as:struct K-aryTreeNode| char data; struct K-aryTreeNode *child]}; i int “Ind = 0; struct K-aryTreeNode *BuildK-aryTree(char Al], int n, int k} if{n<=0) return NULL; struct K-aryTreeNode *newNode = (struct K-aryTreeNode') malloc(sizeof{struct K-aryTreeNode)}; iffnewNode) | printff'Memory Error’); return; \ i newNode-child = (struct K-aryTreeNode*) malloc{ k * sizeof|struct K-aryTreeNode)); iflinewNode-child) { printt("Memory Exror’); return; \ newNode--data = Alind}; for (int i= 0; isk; iH) { iffk * Ind +4 from the stack (T; is popped first) and form a new tree whose root is the operator and whose left and right children point to Ty and T, respectively. A pointer to this new tree is then pushed onto the stack.As an example, assume the input is AB C*+ D /. The first three symbols are operands, so create tree nocles and push pointers to them onto a stack as shown below. ‘Next, an operator ©* is read, so two pointers to trees are popped, a new tee is formed and a pointer to it is pushed onto the stack. ‘Next, an operator ‘+ is read, so two pointers to trees are popped, a new tree is formed and a pointer to it is pushed onto the stack. ‘Next, an operand ‘D’ is read, a one-node tree is created and a pointer to the corresponding tree is pushed onto the stack.Finally, the last symbol (*/”) is read, two trees are merged and a pointer to the final tree is left on the stack, 6.10 XOR Trees ‘This concept is similar to memory efficient doubly linked lists of Linked Lists chapter. Also, like threaded binary trees this representation does not neecl stacks or queues for traversing the trees. This representation is used for traversing back (to parent) and forth (to children) using @ operation, To represent the same in XOR trees, for each node below are the mules used for representation: . Each nodes left will have the ® of its parent and its left children, + Each nodes right will have the © of its parent and its right children. + The root nodes parent is NULL and also leaf nodes children are NULL nodes,