Question Design an algorithm to verify that a tree is a universal value binary tree. Universal value binary tree means all value in that tree is the same. Solution There is two approach for this problem. One is with recursive function and another is with iterative function. For this problem,…

Question Given a number, find the number of 1 in the number’s binary expression. For example, binary express of 10 is 1010. So the number of 1 in it is 2. Solution To solve this, we can check each bit by shifting the bits one by one. 1010 -&…

Question Verify whether all nodes have the same value in a binary tree. Solution We can traverse the tree with our usual way, like depth-first or breadth-first algorithm. Then pass a value, probably the root value, to compare with the visiting node. Example node structure class bst_node: value = None…

Question Print a binary tree layer-by-layer from top to bottom, and from left to right for each layer. Solution Yes, it’s a simple task. We can use breadth-first search, and which means we need a queue, see reference. levelorder(root) q = empty queue q.enqueue(root) while not q.…

Question Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree. Solution First, to do it in recursive method, we can perform…

Question Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest…

Question Construct an algorithm to verify if a set of numbers is the post-order search result of a binary search tree. Let the figure at the right hand side as an example, the algorithm will return true if {5, 7, 6, 9, 11, 10, 8}. However, it will return false…

Question Convert binary search tree into doubly linked list. It’s required not to create any new node, but only turning pointers. Solution The following shows the concept of this question. 8 / 6 0 -> 5 = 6 = 7 = 8 = 9 = 0 = 1 / / 5 7 9 1 First, since node…