2096. Step-By-Step Directions From a Binary Tree Node to Another

MediumTreeDepth-First SearchStringBinary Tree

Problem Description

You have a binary tree where each node has a unique value from 1 to n. Given two values - startValue (the starting node) and destValue (the destination node) - you need to find the shortest path between these two nodes.

The path should be represented as a string using three types of moves:

'L' - move from current node to its left child
'R' - move from current node to its right child
'U' - move from current node to its parent

The solution works by first finding the Lowest Common Ancestor (LCA) of the start and destination nodes. The LCA is the deepest node that is an ancestor of both nodes.

Once we have the LCA, we find two paths:

Path from LCA to startValue
Path from LCA to destValue

To get from startValue to destValue, we need to:

First go UP from startValue to the LCA (this requires as many 'U' moves as the length of the path from LCA to start)
Then go DOWN from LCA to destValue (following the actual path with 'L' and 'R' moves)

For example, if the path from LCA to start is ['L', 'R'] and the path from LCA to destination is ['R', 'L'], the final answer would be "UU" + "RL" = "UURL" - go up twice to reach the LCA, then right and left to reach the destination.

The lca function finds the lowest common ancestor using recursion. The dfs function finds the path from a given node to a target value by exploring left and right subtrees, backtracking when necessary.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

Yes: The problem explicitly states we're working with a binary tree structure.

DFS

We arrive at DFS: Since we're dealing with a tree structure, the flowchart directs us to use Depth-First Search.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

This aligns perfectly with the solution approach, which uses DFS in two key ways:

Finding the Lowest Common Ancestor (LCA): The lca function uses DFS to recursively traverse the tree and find the deepest node that is an ancestor of both the start and destination nodes.
Finding paths from LCA to target nodes: The dfs function uses DFS with backtracking to find the path from the LCA to both the start and destination values, trying left and right subtrees and backtracking when necessary.

The DFS pattern is ideal here because:

We need to explore the tree structure deeply to find specific nodes
We need to track paths through the tree (which DFS naturally does via recursion)
The problem requires traversing from one node to another through parent-child relationships, which is a classic tree traversal scenario

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that to find the shortest path between any two nodes in a tree, we must go through their Lowest Common Ancestor (LCA). Why? Because in a tree, there's only one path between any two nodes, and that path must pass through their common ancestor.

Think of it like finding directions between two locations in a family tree. If you want to go from one cousin to another, you'd first need to trace back up to their common grandparent, then trace down to the other cousin.

Here's how we can visualize the journey:

From the start node, we need to go UP to reach the LCA
From the LCA, we need to go DOWN to reach the destination

The challenge is that we can only move using 'L', 'R', and 'U' commands. So our strategy becomes:

First, find the LCA of both nodes
Find the path from LCA to the start node (this tells us how many steps UP we need)
Find the path from LCA to the destination node (this gives us the exact 'L' and 'R' moves needed)

For the path from start to LCA, we don't actually need the exact moves - we just need to know the length. Since we're going backwards (from child to ancestor), every move is an 'U'. If the path from LCA to start has length 3, we need "UUU" to go back up.

For the path from LCA to destination, we need the exact sequence of 'L' and 'R' moves to navigate down the tree.

The beauty of this approach is that it guarantees the shortest path because:

There's only one path between any two nodes in a tree
Going through the LCA is the only way to connect them
We're not taking any unnecessary detours

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Implementation

1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8from typing import Optional, List 9 10 11class Solution: 12 def getDirections( 13 self, root: Optional[TreeNode], startValue: int, destValue: int 14 ) -> str: 15 """ 16 Find the shortest path directions from start node to destination node in a binary tree. 17 Returns a string of 'U' (up), 'L' (left), and 'R' (right) movements. 18 """ 19 20 def find_lca(node: Optional[TreeNode], p: int, q: int) -> Optional[TreeNode]: 21 """ 22 Find the Lowest Common Ancestor (LCA) of two nodes with values p and q. 23 24 Args: 25 node: Current node in the tree 26 p: Value of first target node 27 q: Value of second target node 28 29 Returns: 30 The LCA node or None if not found 31 """ 32 # Base case: reached null or found one of the target nodes 33 if node is None or node.val in (p, q): 34 return node 35 36 # Recursively search in left and right subtrees 37 left_result = find_lca(node.left, p, q) 38 right_result = find_lca(node.right, p, q) 39 40 # If both subtrees return non-null, current node is the LCA 41 if left_result and right_result: 42 return node 43 44 # Otherwise, return the non-null result (or None if both are null) 45 return left_result or right_result 46 47 def find_path(node: Optional[TreeNode], target: int, path: List[str]) -> bool: 48 """ 49 Find the path from current node to target node using DFS. 50 51 Args: 52 node: Current node in the tree 53 target: Value of the target node to find 54 path: List to store the path directions ('L' or 'R') 55 56 Returns: 57 True if target is found, False otherwise 58 """ 59 # Base case: reached null node 60 if node is None: 61 return False 62 63 # Found the target node 64 if node.val == target: 65 return True 66 67 # Try going left 68 path.append("L") 69 if find_path(node.left, target, path): 70 return True 71 72 # Left path didn't work, try going right 73 path[-1] = "R" 74 if find_path(node.right, target, path): 75 return True 76 77 # Neither left nor right worked, backtrack 78 path.pop() 79 return False 80 81 # Step 1: Find the lowest common ancestor of start and destination nodes 82 lca_node = find_lca(root, startValue, destValue) 83 84 # Step 2: Find paths from LCA to both start and destination 85 path_to_start: List[str] = [] 86 path_to_dest: List[str] = [] 87 88 find_path(lca_node, startValue, path_to_start) 89 find_path(lca_node, destValue, path_to_dest) 90 91 # Step 3: Build result - go up from start to LCA, then follow path to destination 92 # Number of 'U' moves equals the length of path from LCA to start 93 return "U" * len(path_to_start) + "".join(path_to_dest) 94

1class Solution { 2 /** 3 * Finds the shortest path directions from startValue to destValue in a binary tree. 4 * Returns a string where 'U' means go up to parent, 'L' means go left, 'R' means go right. 5 * 6 * @param root The root of the binary tree 7 * @param startValue The starting node value 8 * @param destValue The destination node value 9 * @return String representing the path from start to destination 10 */ 11 public String getDirections(TreeNode root, int startValue, int destValue) { 12 // Find the Lowest Common Ancestor (LCA) of start and destination nodes 13 TreeNode lcaNode = lca(root, startValue, destValue); 14 15 // Build paths from LCA to both start and destination nodes 16 StringBuilder pathToStart = new StringBuilder(); 17 StringBuilder pathToDest = new StringBuilder(); 18 19 // Find path from LCA to start node 20 dfs(lcaNode, startValue, pathToStart); 21 22 // Find path from LCA to destination node 23 dfs(lcaNode, destValue, pathToDest); 24 25 // Convert path to start into 'U' moves (going up from start to LCA) 26 // then append the path from LCA to destination 27 return "U".repeat(pathToStart.length()) + pathToDest.toString(); 28 } 29 30 /** 31 * Finds the Lowest Common Ancestor (LCA) of two nodes with values p and q. 32 * 33 * @param node Current node being examined 34 * @param p First target value 35 * @param q Second target value 36 * @return The LCA node of nodes with values p and q 37 */ 38 private TreeNode lca(TreeNode node, int p, int q) { 39 // Base case: if node is null or matches either target value 40 if (node == null || node.val == p || node.val == q) { 41 return node; 42 } 43 44 // Recursively search in left and right subtrees 45 TreeNode leftResult = lca(node.left, p, q); 46 TreeNode rightResult = lca(node.right, p, q); 47 48 // If both subtrees return non-null, current node is the LCA 49 if (leftResult != null && rightResult != null) { 50 return node; 51 } 52 53 // Otherwise, return the non-null result (or null if both are null) 54 return leftResult != null ? leftResult : rightResult; 55 } 56 57 /** 58 * Performs DFS to find the path from current node to target value x. 59 * Builds the path string with 'L' for left moves and 'R' for right moves. 60 * 61 * @param node Current node being examined 62 * @param targetValue The target value to find 63 * @param path StringBuilder to accumulate the path 64 * @return true if target is found, false otherwise 65 */ 66 private boolean dfs(TreeNode node, int targetValue, StringBuilder path) { 67 // Base case: node is null, target not found 68 if (node == null) { 69 return false; 70 } 71 72 // Target found at current node 73 if (node.val == targetValue) { 74 return true; 75 } 76 77 // Try going left: append 'L' and search left subtree 78 path.append('L'); 79 if (dfs(node.left, targetValue, path)) { 80 return true; 81 } 82 83 // Left path didn't work, try right: change last character to 'R' 84 path.setCharAt(path.length() - 1, 'R'); 85 if (dfs(node.right, targetValue, path)) { 86 return true; 87 } 88 89 // Neither path worked, backtrack by removing the last character 90 path.deleteCharAt(path.length() - 1); 91 return false; 92 } 93} 94

1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12class Solution { 13public: 14 /** 15 * Find the shortest path directions from startValue to destValue in a binary tree 16 * @param root - The root of the binary tree 17 * @param startValue - The value of the starting node 18 * @param destValue - The value of the destination node 19 * @return A string of directions where 'U' means go up to parent, 'L' means go left, 'R' means go right 20 */ 21 string getDirections(TreeNode* root, int startValue, int destValue) { 22 // Step 1: Find the Lowest Common Ancestor (LCA) of start and destination nodes 23 TreeNode* lcaNode = findLCA(root, startValue, destValue); 24 25 // Step 2: Find the path from LCA to start node 26 string pathToStart; 27 findPathDFS(lcaNode, startValue, pathToStart); 28 29 // Step 3: Find the path from LCA to destination node 30 string pathToDest; 31 findPathDFS(lcaNode, destValue, pathToDest); 32 33 // Step 4: Convert path to start into 'U' moves (going up from start to LCA) 34 // Then append the path from LCA to destination 35 return string(pathToStart.size(), 'U') + pathToDest; 36 } 37 38private: 39 /** 40 * Find the Lowest Common Ancestor of two nodes with values nodeVal1 and nodeVal2 41 * @param node - Current node being examined 42 * @param nodeVal1 - Value of the first target node 43 * @param nodeVal2 - Value of the second target node 44 * @return The LCA node, or nullptr if not found 45 */ 46 TreeNode* findLCA(TreeNode* node, int nodeVal1, int nodeVal2) { 47 // Base case: reached null or found one of the target nodes 48 if (node == nullptr || node->val == nodeVal1 || node->val == nodeVal2) { 49 return node; 50 } 51 52 // Recursively search in left and right subtrees 53 TreeNode* leftResult = findLCA(node->left, nodeVal1, nodeVal2); 54 TreeNode* rightResult = findLCA(node->right, nodeVal1, nodeVal2); 55 56 // If both subtrees return non-null, current node is the LCA 57 if (leftResult != nullptr && rightResult != nullptr) { 58 return node; 59 } 60 61 // Otherwise, return the non-null result (if any) 62 return leftResult != nullptr ? leftResult : rightResult; 63 } 64 65 /** 66 * Find the path from current node to target value using DFS 67 * @param node - Current node being examined 68 * @param targetValue - The value we're searching for 69 * @param path - String to store the path (modified by reference) 70 * @return true if target is found in this subtree, false otherwise 71 */ 72 bool findPathDFS(TreeNode* node, int targetValue, string& path) { 73 // Base case: reached null node 74 if (node == nullptr) { 75 return false; 76 } 77 78 // Found the target node 79 if (node->val == targetValue) { 80 return true; 81 } 82 83 // Try going left: add 'L' to path 84 path.push_back('L'); 85 if (findPathDFS(node->left, targetValue, path)) { 86 return true; // Target found in left subtree 87 } 88 89 // Left didn't work, try going right: replace 'L' with 'R' 90 path.back() = 'R'; 91 if (findPathDFS(node->right, targetValue, path)) { 92 return true; // Target found in right subtree 93 } 94 95 // Target not found in either subtree, backtrack 96 path.pop_back(); 97 return false; 98 } 99}; 100

1/** 2 * Definition for a binary tree node. 3 * class TreeNode { 4 * val: number 5 * left: TreeNode | null 6 * right: TreeNode | null 7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { 8 * this.val = (val===undefined ? 0 : val) 9 * this.left = (left===undefined ? null : left) 10 * this.right = (right===undefined ? null : right) 11 * } 12 * } 13 */ 14 15/** 16 * Finds the lowest common ancestor (LCA) of two nodes with values p and q 17 * @param node - Current node in the tree 18 * @param p - Value of the first target node 19 * @param q - Value of the second target node 20 * @returns The LCA node or null if not found 21 */ 22function findLowestCommonAncestor(node: TreeNode | null, p: number, q: number): TreeNode | null { 23 // Base case: if node is null or matches either target value 24 if (node === null || node.val === p || node.val === q) { 25 return node; 26 } 27 28 // Recursively search in left and right subtrees 29 const leftResult: TreeNode | null = findLowestCommonAncestor(node.left, p, q); 30 const rightResult: TreeNode | null = findLowestCommonAncestor(node.right, p, q); 31 32 // If both left and right return non-null, current node is the LCA 33 if (leftResult !== null && rightResult !== null) { 34 return node; 35 } 36 37 // Otherwise, return whichever side found a target node 38 return leftResult !== null ? leftResult : rightResult; 39} 40 41/** 42 * Performs depth-first search to find path from current node to target value 43 * @param node - Current node in the tree 44 * @param targetValue - The value we're searching for 45 * @param path - Array to store the path directions ('L' for left, 'R' for right) 46 * @returns true if target is found, false otherwise 47 */ 48function findPathToTarget(node: TreeNode | null, targetValue: number, path: string[]): boolean { 49 // Base case: node is null 50 if (node === null) { 51 return false; 52 } 53 54 // Target found 55 if (node.val === targetValue) { 56 return true; 57 } 58 59 // Try going left 60 path.push('L'); 61 if (findPathToTarget(node.left, targetValue, path)) { 62 return true; 63 } 64 65 // If left didn't work, try going right 66 path[path.length - 1] = 'R'; 67 if (findPathToTarget(node.right, targetValue, path)) { 68 return true; 69 } 70 71 // Neither direction worked, backtrack 72 path.pop(); 73 return false; 74} 75 76/** 77 * Finds the shortest path directions from startValue to destValue in a binary tree 78 * @param root - Root of the binary tree 79 * @param startValue - Starting node value 80 * @param destValue - Destination node value 81 * @returns String of directions: 'U' for up, 'L' for left, 'R' for right 82 */ 83function getDirections(root: TreeNode | null, startValue: number, destValue: number): string { 84 // Find the lowest common ancestor of start and destination nodes 85 const lowestCommonAncestor: TreeNode | null = findLowestCommonAncestor(root, startValue, destValue); 86 87 // Find path from LCA to start node 88 const pathFromLCAToStart: string[] = []; 89 findPathToTarget(lowestCommonAncestor, startValue, pathFromLCAToStart); 90 91 // Find path from LCA to destination node 92 const pathFromLCAToDestination: string[] = []; 93 findPathToTarget(lowestCommonAncestor, destValue, pathFromLCAToDestination); 94 95 // Convert path to start into 'U' moves (going up from start to LCA) 96 // Then append the path from LCA to destination 97 const upMoves: string = 'U'.repeat(pathFromLCAToStart.length); 98 const downMoves: string = pathFromLCAToDestination.join(''); 99 100 return upMoves + downMoves; 101} 102

Solution Approach

The solution implements the strategy we identified using two main functions:

1. Finding the Lowest Common Ancestor (LCA)

The lca function uses a recursive DFS approach:

Base case: If the current node is None or matches either startValue or destValue, return the current node
Recursively search left and right subtrees
If both left and right subtrees return non-null values, the current node is the LCA (both values are in different subtrees)
Otherwise, return whichever subtree contains the value(s)

def lca(node, p, q):  if node is None or node.val in (p, q):  return node  left = lca(node.left, p, q)  right = lca(node.right, p, q)  if left and right:  return node  return left or right

2. Finding the Path from a Node to a Target

The dfs function finds the path from a given node to a target value using backtracking:

If we find the target, return True
Try going left by appending 'L' to the path
If left doesn't work, replace the last character with 'R' and try right
If neither works, pop the character and backtrack

def dfs(node, x, path):  if node.val == x:  return True  path.append("L")  if dfs(node.left, x, path):  return True  path[-1] = "R" # Replace 'L' with 'R'  if dfs(node.right, x, path):  return True  path.pop() # Backtrack  return False

3. Combining the Results

Once we have:

The LCA node
Path from LCA to startValue (e.g., ['L', 'R'])
Path from LCA to destValue (e.g., ['R', 'L'])

We construct the final answer:

Convert the length of path_to_start into that many 'U' moves (going up from start to LCA)
Append the exact path from LCA to destination

return "U" * len(path_to_start) + "".join(path_to_dest)

The time complexity is O(n) where n is the number of nodes, as we potentially visit each node a constant number of times. The space complexity is O(h) where h is the height of the tree, due to the recursion stack and path storage.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Consider this binary tree:

 5  / \  1 2  / / \  3 6 4

We want to find the path from startValue = 3 to destValue = 6.

Step 1: Find the Lowest Common Ancestor (LCA)

Starting from root (5), we search for nodes 3 and 6:

At node 5: Check left subtree (contains 3) and right subtree (contains 6)
Left subtree returns node 1 (ancestor of 3)
Right subtree returns node 2 (ancestor of 6)
Since both subtrees return non-null, node 5 is the LCA

Step 2: Find Path from LCA to Start (5 → 3)

Starting from LCA (5), find path to node 3:

Try left: Go to node 1 (append 'L')
From node 1, try left: Go to node 3 (append 'L')
Found target! Path = ['L', 'L']

Step 3: Find Path from LCA to Destination (5 → 6)

Starting from LCA (5), find path to node 6:

Try left: Go to node 1 (append 'L')
Node 1 has only left child (3), not our target
Backtrack, replace 'L' with 'R': Go to node 2
From node 2, try left: Go to node 6 (append 'L')
Found target! Path = ['R', 'L']

Step 4: Construct Final Answer

Path from LCA to start: ['L', 'L'] → Length is 2, so we need "UU" to go up
Path from LCA to destination: ['R', 'L'] → Use "RL" to go down
Final answer: "UU" + "RL" = "UURL"

This means: From node 3, go up twice to reach node 5 (the LCA), then go right to node 2, then left to reach node 6.

Let's verify: 3 → (U) → 1 → (U) → 5 → (R) → 2 → (L) → 6 ✓

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main operations:

Finding the Lowest Common Ancestor (LCA): The lca function visits each node at most once in the worst case, resulting in O(n) time complexity.
Finding path from LCA to startValue: The dfs function traverses the tree to find the target node, visiting each node at most once, which takes O(n) time in the worst case.
Finding path from LCA to destValue: Similarly, this also takes O(n) time in the worst case.

Since these operations are performed sequentially, the overall time complexity is O(n) + O(n) + O(n) = O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(n)

The space complexity comes from:

Recursion stack space: Both lca and dfs functions use recursion. In the worst case (skewed tree), the recursion depth can be O(n).
Path storage: The path_to_start and path_to_dest lists store the paths from LCA to the respective nodes. In the worst case, these paths can have length O(n).
The final result string construction also takes O(n) space in the worst case.

Therefore, the overall space complexity is O(n), where n is the number of nodes in the binary tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling the Case When Start or Destination is the LCA

One common pitfall is not properly handling the edge case where either the startValue or destValue is itself the LCA. When the LCA function returns early because it finds one of the target nodes, that node might actually be the ancestor of the other node.

Problem Example: Consider a tree where node 5 is the parent of node 3:

 5 (startValue)  /  3 (destValue)

The LCA function will return node 5 immediately upon finding it, which is correct. However, if we're not careful with the path finding, we might get incorrect results.

Solution: The current implementation handles this correctly by:

The LCA function properly returns the ancestor node even if it's one of the targets
The find_path function will return an empty path when searching from the LCA to itself (if start is the LCA)
The final result correctly uses "U" * 0 (empty string) when the path from LCA to start is empty

2. Mutating the Path List Incorrectly During Backtracking

A subtle but critical pitfall occurs in the find_path function with the line path[-1] = "R". Developers might mistakenly write:

# WRONG approach: path.append("L") if find_path(node.left, target, path):  return True path.pop() # Remove 'L' path.append("R") # Add 'R' if find_path(node.right, target, path):  return True path.pop() # Remove 'R'

Why this is inefficient: This performs unnecessary list operations (pop and append) when switching from left to right exploration.

Correct approach (as in the solution):

path.append("L") if find_path(node.left, target, path):  return True path[-1] = "R" # Simply replace 'L' with 'R' if find_path(node.right, target, path):  return True path.pop() # Only pop once at the end

This optimization reduces the number of list operations and makes the code cleaner.

3. Not Handling Null Nodes in the DFS Path Finding

A common mistake is forgetting to check for null nodes in the find_path function:

Wrong:

def find_path(node, target, path):  if node.val == target: # This will crash if node is None!  return True  # ... rest of the code

Correct (as in the solution):

def find_path(node, target, path):  if node is None: # Check for None first  return False  if node.val == target:  return True  # ... rest of the code

4. Assuming the Tree Structure Without Validation

The solution assumes that both startValue and destValue exist in the tree and are unique. In a production environment, you should validate:

Both values actually exist in the tree
The tree is properly formed (no cycles, proper parent-child relationships)

Enhanced validation approach:

def getDirections(self, root, startValue, destValue):  # First, verify both nodes exist  def node_exists(node, value):  if not node:  return False  if node.val == value:  return True  return node_exists(node.left, value) or node_exists(node.right, value)   if not node_exists(root, startValue) or not node_exists(root, destValue):  return "" # Or raise an exception   # Continue with the main logic...

5. String Concatenation Performance Issues

While the current solution is fine for typical tree sizes, for very deep trees with long paths, string concatenation could become a performance bottleneck:

Current approach:

return "U" * len(path_to_start) + "".join(path_to_dest)

For extremely large paths, consider using a list:

result = [] result.extend(['U'] * len(path_to_start)) result.extend(path_to_dest) return "".join(result)

This approach is more memory-efficient for very large strings, though the difference is negligible for typical problem constraints.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target): 2 left, right = 0, len(arr) - 1 3 while left ___ right: 4 mid = (left + right) // 2 5 if arr[mid] == target: 6 return mid 7 if arr[mid] < target: 8 ___ = mid + 1 9 else: 10 ___ = mid - 1 11 return -1 12

1public static int binarySearch(int[] arr, int target) { 2 int left = 0; 3 int right = arr.length - 1; 4 5 while (left ___ right) { 6 int mid = left + (right - left) / 2; 7 if (arr[mid] == target) return mid; 8 if (arr[mid] < target) { 9 ___ = mid + 1; 10 } else { 11 ___ = mid - 1; 12 } 13 } 14 return -1; 15} 16

1function binarySearch(arr, target) { 2 let left = 0; 3 let right = arr.length - 1; 4 5 while (left ___ right) { 6 let mid = left + Math.trunc((right - left) / 2); 7 if (arr[mid] == target) return mid; 8 if (arr[mid] < target) { 9 ___ = mid + 1; 10 } else { 11 ___ = mid - 1; 12 } 13 } 14 return -1; 15} 16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know