findKthSmallestValue in a Binary Tree.

BinaryTree.java

package de.jungblut.interviews;

import java.util.Stack;

import com.google.common.base.Preconditions;

public class BinaryTree {

	class TreeNode {
		TreeNode left;
		TreeNode right;
		int value;
	}

	TreeNode root;

	public void buildFromSortedArray(int[] array) {
		Preconditions.checkNotNull(array);
		root = buildFromSortedArray(array, 0, array.length - 1);
	}

	private TreeNode buildFromSortedArray(int[] array, int start, int end) {
		if (start > end)
			return null;
		final int mid = (start + end) >>> 1;
		TreeNode node = new TreeNode();
		node.value = array[mid];
		node.left = buildFromSortedArray(array, start, mid - 1);
		node.right = buildFromSortedArray(array, mid + 1, end);
		return node;
	}

	private int findKthSmallestValue(int k) {
		TreeNode start = root;
		Stack<TreeNode> parents = new Stack<>();
		while (!parents.isEmpty() || start != null) {
			if (start != null) {
				parents.add(start);
				start = start.left;
			} else {
				start = parents.pop();
				// here we decrement k until we hit zero, which is the kth
				// smallest
				k--;
				if (k == 0) {
					return start.value;
				}
				start = start.right;
			}
		}

		return -1; // not found
	}

	public static void main(String[] args) {
		// construct a simple tree
		BinaryTree tree = new BinaryTree();

		tree.buildFromSortedArray(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

		int result = tree.findKthSmallestValue(3);
		System.out.println(result);

	}

}