Median of BST

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find median of BST. In-order traversal gives sorted sequence; pick middle element(s).

Algorithm

1Count total nodes n. In-order traversal: when counter reaches (n+1)/2 (and n/2 if even): record values.

Common Pitfalls

•Two-pass: count nodes, then in-order to find median. Or Morris traversal for O(1) space.

Median of BST.java

Java

// Approach: In-order traversal to flatten BST. Middle element is the median.
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left;
    Node right;

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

class Solution {
    public int findMedian(Node root) {
        dfs(root);
        if (res.size() % 2 == 0)
            return res.get((res.size() - 1) / 2);
        return res.get((res.size()) / 2);
    }

    ArrayList<Integer> res = new ArrayList<>();

    void dfs(Node root) {
        if (root == null)
            return;
        dfs(root.left);
        res.add(root.data);
        dfs(root.right);
    }
}

Was this solution helpful?