My software development journey
Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below. If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1. 1 / \ 2 3 / \ / \ 4 5 6 7 Given two nodes from…
Given a binary tree, how to convert it to it’s mirror image?For example consider the following binary tree and it’s mirror image. Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can…
Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other. For example Let us…
Given a binary tree, how do we print the nodes in level order starting from the bottom. For example for the following tree, the output should be 2 3 1 1 / 2 3An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level…
Given a binary tree, how do we check if it is balanced or not? We say that a binary tree is balanced if height difference of left and the right sub-trees is at most 1 at any node. Consider the following examples 1 1 1 1 / / …
Given a binary search tree, how do we find a kth smallest or kth largest element? For example, given the following binary search tree. Third largest element is 6 Second smallest element is 2 Fifth largest element is 5 and so on… Solution: We can solve this problem by modifying the the in-order traversal method…
Given a binary tree, how do we print the right view of it?For example, consider the simple binary tree below 1 / 2 3 The right view of this is 1, 3. Similarly consider one more example 1 / 2 5 / 3 4 Right view for this tree contains…
Given a binary tree, how do we print the left view of it?For example, consider the simple binary tree below 1 / 2 3 The left view of this is 1, 2. Similarly consider one more example 1 / 2 3 / 4 5Left view for this tree contains 1, 2,…
Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.For example consider the below binary tree The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7.…
Given the in-order, and pre-order or post-order sequences of a binary tree, how do we construct a binary tree from them?Given only pre-order and post order traversals, we can not construct a unique binary tree from them.For example given In-order : {1, 2, 3, 4, 5, 6, 7, 8}Pre-order: {5, 3, 2, 1, 4, 8, 6,…