FastPrepInorder Predecessor in a BST
Problems/Inorder Predecessor in a BST

Inorder Predecessor in a BST

Nutanix logoNutanix● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A Nutanix intern candidate reported a second-round phone interview with concept questions and two coding questions. According to the report, the second coding question wanted the node just before a chosen node in inorder (sorted) order. The chosen node is given as a pointer into a binary search tree.

The report gives no limits, no examples and no rule for when nothing comes before the chosen node. Here we chose the following. The chosen node is named by its value instead of a pointer, so all values are different. The function returns the value of the node before it, or -1 when there is none. The tree has 1 to 2000 nodes with values from 0 to 10^5 and may be a long chain. The examples are ours.

Our version is about 80% the same as the reported question.

You are given the root of a binary search tree and an integer target. All node values are different. For every node, each value in its left subtree is smaller than the node's value and each value in its right subtree is larger. target is the value of one node in the tree; call it the target node.

Return the value of the node that comes just before the target node in inorder, which is the order from smallest value to largest. If the target node holds the smallest value in the tree, nothing comes before it: return -1.

Function

inorderPredecessor(root: TreeNode, target: int) → int

Examples

Example 1

root = [20,10,30,5,15,null,40]target = 20return = 15
root
20105153040

In order, the values are 5, 10, 15, 20, 30, 40. The value just before 20 is 15. In the tree, 15 is the rightmost node of 20's left subtree.

Example 2

root = [20,10,30,5,15,null,40]target = 30return = 20
root
20105153040

Node 30 has no left child, so the node before it is above it. Going up from 30, the first ancestor that 30 is to the right of is the root 20. In order, 20 is indeed just before 30.

Example 3

root = [8,null,12,9]target = 8return = -1
root
8129

The tree is 8 with right child 12, and 12 has left child 9. In order the values are 8, 9, 12. 8 is the smallest value, so nothing comes before it and the answer is -1.

Constraints

  • The number of nodes is between 1 and 2000.
  • 0 <= node.val <= 10^5
  • No two nodes have the same value, and the tree follows the binary search tree rule.
  • target is the value of a node in the tree.
  • The tree does not have to be balanced. It can be a single chain, so its height can equal its number of nodes.

More Nutanix Phone Screen questions

  • Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
  • Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
  • Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
  • Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
  • Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
  • Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
  • Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
  • Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
  • K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
  • Odd Numbers Up and BackPHONE SCREEN · Seen Jan 2019

Similar questions at other companies

  • Add All Larger Values in a BSTAdobe · PHONE SCREENAdobe interview questions
  • Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
  • Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
  • Check the Order of a Binary Search TreeCapital One · ONSITE INTERVIEWCapital One interview questions
  • N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • House Robber IIIOkta · PHONE SCREENOkta interview questions
  • Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
  • Validate Binary Search TreeKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
  • House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
  • Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions

Interview reports that mention this question

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)

Nutanix interview experiences

  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
  • Nutanix Intern Debugging Round and Interviews: 25 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int inorderPredecessor(TreeNode root, int target) {
        // Write your code here.
    }
}
Checking account…