• LeetCode Recover Binary Search Tree (java)

    Two elements of a binary search tree (BST) are swapped by mistake.

    Recover the tree without changing its structure.

    A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

    Java Solution

    We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

    If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,

    [Read More...]
  • Leetcode – Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.


    This problem can be easily solved using a recursive algorithm.  As

    maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right) + 1 if root != null;

    and maxDepth(root) == 0 if root == null;

    Java solution:



    [Read More...]
  • LeetCode – Binary Search Tree Iterator (Java)

    Binary Search Tree Iterator

    • Difficulty: Medium

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    Calling next() will return the next smallest number in the BST.

    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    Source: https://leetcode.com/problems/binary-search-tree-iterator/

    In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

    [Read More...]