Continuing from our last post for a Generic Binary Tree implementation, we’ve come up with a solution to quite an interesting problem.
We define a path in a binary tree to be a non-empty sequence of nodes that one can traverse by following the pointers in the nodes. A path only goes to the right if following this path we traverse only the right sub-tree pointers in nodes. Similarly it can be defined for a path going only to the left. We use the term unidirectional for such paths.
The problem here is to find the maximal length of any such unidirectional path that exists in a given tree. The output will be -1 if the tree is empty, and will be 0 if the tree has only the root node.
For the tree shown below:
Binary Tree: maximal unidirectional path to be found
there are multiple maximal unidirectional paths that exist in it. These are 5,3,4,6 (going left only starting from root), 5,10,11,13 (going right only) and 12,20,22,23 (again going right only but not beginning at the root). The output of code for finding the maximal unidirectional path length in each case would be 3 as three pointers/ links are to be traversed in each path.
This code is presented as part of the earlier GenericBinaryTree class’s code only. The earlier implementation can be found here.
Here goes the code for finding the same:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/** * Implementation of a GenericBinaryTree with <code>int</code> type data. * The nodes are of type {@link BinaryTreeNode}. * * @author team Coddicted * */ public class GenericBinaryTree { //... earlier code goes here //... /** * To get the maximum unidirectional path length in the given * tree. * * @param root * @return * Number of nodes traversed in any maximal unidirectional path * in the given tree (represented by its root node). */ public int getMaxUniDirectPath(BinaryTreeNode root){ if(root == null) return -1; return findMaxUniDirectHeight(root, 0, 0); } /** * @param root * @param leftHeight * @param rightHeight * @return */ private int findMaxUniDirectHeight(BinaryTreeNode root,int leftHeight, int rightHeight) { int subLHeight, subRHeight; if(root==null){ return 0; } else { subLHeight = findMaxUniDirectHeight(root.leftNode, leftHeight + 1, 0); subRHeight = findMaxUniDirectHeight(root.rightNode, 0, rightHeight + 1); if(subLHeight > leftHeight) leftHeight = subLHeight; if(subRHeight > rightHeight) rightHeight = subRHeight; if(leftHeight > rightHeight){ return leftHeight; } else { return rightHeight; } } } } |
For using the above code a single statement is required after having created the tree itself:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
import com.coddicted.ds.BinaryTreeNode; import com.coddicted.ds.GenericBinaryTree; public class GenericBinaryTreeUser { public static void main(String[] args) { GenericBinaryTree gbt = new GenericBinaryTree(); BinaryTreeNode root = new BinaryTreeNode(); root.x = 5; gbt.insertIntoGenericBinaryTree(root, 3,"l"); gbt.insertIntoGenericBinaryTree(root, 4,"ll"); gbt.insertIntoGenericBinaryTree(root, 6,"lll"); gbt.insertIntoGenericBinaryTree(root, 10, "r"); gbt.insertIntoGenericBinaryTree(root, 11, "rr"); gbt.insertIntoGenericBinaryTree(root, 13, "rrr"); gbt.insertIntoGenericBinaryTree(root, 12, "rl"); gbt.insertIntoGenericBinaryTree(root, 21, "rll"); gbt.insertIntoGenericBinaryTree(root, 20, "rlr"); gbt.insertIntoGenericBinaryTree(root, 22, "rlrr"); gbt.insertIntoGenericBinaryTree(root, 23, "rlrrr"); gbt.insertIntoGenericBinaryTree(root, 24, "rlrrrl"); System.out.println(gbt.getMaxUniDirectPath(root)); } } |
Notice that the above code is also a modification to the previous code only which is also present in the previous post.
Ԝay cool! Some very valid рoints! I appreciate you writing this post and also
the rest of the site is alѕo reallү good.