Binary Search Tree | Learn for Master

LeetCode Recover Binary Search Tree (java)

August 28, 2016 Author: david
No comment yet

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

Recover the tree without changing its structure.

Note:
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

August 7, 2016 Author: david

No comment yet

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.

Analysis:

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:

//Definition for a binary tree node.
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}
class MaxDepth {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }
}

//Definition for a binary tree node.

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

class MaxDepth {

public int maxDepth(TreeNode root) {

if(root == null) return 0;

int leftMaxDepth = maxDepth(root.left);

int rightMaxDepth = maxDepth(root.right);

return Math.max(leftMaxDepth, rightMaxDepth) + 1;

}

https://leetcode.com/problems/maximum-depth-of-binary-tree/

[Read More...]

LeetCode – Binary Search Tree Iterator (Java)

July 9, 2016 Author: david
No comment yet
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...]