Number of Turns in Binary Tree

Problem Overview

A turn is a left-then-right (or right-then-left) change on the unique path between two nodes.

Intuition

A turn is a left-then-right (or right-then-left) change on the unique path between two nodes. That path always goes up to the LCA and then down. Count direction changes on each leg from the LCA. If the two nodes sit in different subtrees you also pay one extra turn at the LCA itself. If they line up with no change of direction, the platform wants -1 rather than 0.

Algorithm

1If first equals second, return -1.
2Find the LCA of first and second.
3DFS from the LCA: dir 0 at the start, 1 after a left edge, 2 after a right edge. When dir flips, bump the turn count for that walk.
4Record how many turns sit on the path to each target.
5If the LCA is one of the targets, return the other path's turns, or -1 when that value is 0. Otherwise return turnsP + turnsQ + 1.

Example Walkthrough

Input: tree with LCA at 1, first = 2 on a left-left path, second = 3 on a right child

1. Neither target is the LCA, so the path crosses from the left subtree to the right.
2. The left leg may be straight (0 turns). The right leg is a single edge (0 turns).
3. The switch at the LCA adds 1, so the answer is 1.

Output: 1

Common Pitfalls

• Do not count the first edge leaving the LCA as a turn - there is no previous direction yet.
• When one node is an ancestor of the other, the LCA is that ancestor; there is no extra +1 at the LCA.
• A path that never changes direction should return -1, not 0.
• Building two full L/R strings from the root works but uses extra memory; counting from the LCA is enough.

Number of Turns in Binary Tree.java

Java

// Approach: Turns happen when the unique path changes left/right. Find the LCA
// of p and q, then one DFS from the LCA records how many direction changes lie
// on the path to each target. If the LCA is neither target, add 1 for the
// switch at the LCA. A straight path (no turn) is reported as -1.
// Complexity: O(n) time and O(h) space (h = tree height).

class Node {

    int data;
    Node left;
    Node right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {

    public int numberOfTurns(Node root, int first, int second) {
        if (first == second) {
            return -1;
        }

        Node lca = lca(root, first, second);
        if (lca == null) {
            return -1;
        }

        int[] turns = { -1, -1 };
        walk(lca, first, second, 0, 0, turns);

        if (lca.data == first || lca.data == second) {
            int other = lca.data == first ? turns[1] : turns[0];
            return other <= 0 ? -1 : other;
        }
        return turns[0] + turns[1] + 1;
    }

    private Node lca(Node root, int p, int q) {
        if (root == null || root.data == p || root.data == q) {
            return root;
        }
        Node left = lca(root.left, p, q);
        Node right = lca(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    // dir: 0 at LCA, 1 came from a left edge, 2 from a right edge.
    private void walk(Node node, int p, int q, int dir, int soFar, int[] turns) {
        if (node == null || (turns[0] >= 0 && turns[1] >= 0)) {
            return;
        }
        if (node.data == p) {
            turns[0] = soFar;
        }
        if (node.data == q) {
            turns[1] = soFar;
        }
        walk(node.left, p, q, 1, soFar + (dir == 2 ? 1 : 0), turns);
        walk(node.right, p, q, 2, soFar + (dir == 1 ? 1 : 0), turns);
    }
}

Was this solution helpful?