This is a fun little question that will give an interviewer the chance to gauge your understanding of Trees and BSTrees. If wanting more clarification check our binary TreeNode implementation and the wiki on Binary Search Tree.
So first of all to find the next highest node in a BSTree, you should think about clarifications and ambiguities as usual. There are 2 questions 2 mention:
- What are we supposed to return when our given node is the highest in the Tree?
- Do the nodes in our BSTree have a link to their parent?
For the purpose of this question we will assume that we are given clarifications to return null if our given node is the highest and to indeed have a link to our parent.
Finished with clarifications we will head into our algorithm. We have 2 cases we should look into.
How to find the next highest node in a BSTree
- Our node has a right child – In this case find the smallest node in that subtree
- Our node does not have a right child – In this case go upward to search for a parent whose value is bigger
To finish up we are going to provide a simple solution in Java to this question:
|
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 |
/* * @Author: Ajk Palikuqi * * @Question: How to find the next highest node in a BSTree * */ package iqLib.treeLib; public class NextHighestTreeNode { public static TreeNode findNextHighestTreeNode(TreeNode root, TreeNode current) { if (current.getRight() != null) { return findSmallestNodeInTree(current.getRight()); } else { return findBiggerParentNode(current); } } private static TreeNode findSmallestNodeInTree(TreeNode root) { while (root.getLeft() != null) { root = root.getLeft(); } return root; } private static TreeNode findBiggerParentNode(TreeNode root) { while (root.getParent() != null && root.getParent().getLeft() != root) { root = root.getParent(); } return null; } } |
As always you can find the full code in my GitHub Interview Questions repo.
Hope you guys enjoyed it… and I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017