How to find the closest value in a Binary Tree (Not Binary Search Tree) in Java using recursion?


  • 0
    Y

    I was asked during an interview to write a function that find the closest value to int i in a Binary Tree. I was having some trouble coming up with a solution. Can someone help me out? Thanks.


  • 0

    We just have to traverse the whole tree and track the closest value, suppose the root node is not null, here is the Java solution:

    int getClosest(TreeNode root, int target) {
      int closest = root.val;
      
      Stack<TreeNode> stack = new Stack<>();
      stack.push(root);
      
      while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        
        if (Math.abs(node.val - target) < Math.abs(closest - target))
          closest = node.val;
        
        if (node.left != null)
          stack.push(node.left);
        
        if (node.right != null)
          stack.push(node.right);
      }
      
      return closest;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.