Trees

Question 1

Sum of Left Leaves

Answer 1

//Time : O(N)
//Space : O(1)
class Solution{

  public int sumOfLeftLeaves_stack(TreeNode root){
    int result = 0;
    if (root == null) return result;
    Stack stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()){
      TreeNode node = stack.pop();
      if (node != null){
        if (node.left != null && node.left.left == null && node.left.right == null) res += node.val;
        stack.push(node.left);
        stack.push(node.right);
      }
    }
    return res;
  }

  public int sumOfLeftLeaves(TreeNode root){
    return helper(root, false);
  }

public int helper(TreeNode root, boolean isLeft){
if (root == null) return 0;
if (root.left == null && root.right == null && isLeft) return root.val;
int left = helper(root.left, true);
int right = helper(root.right,false);
return left + right;
}
}

Question 2

LCA Binary Tree

Answer 2

//Time : O(N)
//Space : O(1)
class Solution{

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
if (root == null || p == root || q == root) return root;

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;
    if (left != null) return left;
    if (right != null) return right;
    return null;
  }
}

Question 3

LCA Binary Search Tree

Answer 3

//Time : O(N)
//Space : O(1)
class Solution{
  public lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
    if (root.val > p.val && root.val > q.val)
      return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
      return lowestCommonAncestor(root.right, p, q);
    return root;
  }
}

Question 4

Binary Tree Level Order Traversal

Answer 4

//Time : O(N)
//Space : O(N)
class Solution {
    public List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) return result;
        Queue q = new LinkedList<>();
        q.offer(root);

    while(!q.isEmpty()){
      int size = q.size();
      List level = new ArrayList<>();
      for(int i = 0;i

Question 5

Validate Binary Search Tree

Answer 5

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

public boolean helper(TreeNode node, Integer left, Integer right){
  if (node == null) return true;

int val = node.val;
if (left != null && val <= left) return false;
if (right != null && val >= right) return false;

if (! helper(node.right, val, right)) return false;
if (! helper(node.left, left, val)) return false;
return true;
} }

Question 6

Iterative InOrder Traversal

Answer 6

class Solution {
    List list = new ArrayList<>();
    public List inorderTraversal(TreeNode root) {
      if(root == null) return list;
      Stack stack = new Stack<>();
      while(root != null || !stack.isEmpty()){
        while (root != null){
          stack.push(root);
          root = root.left;
        }
        root = stack.pop(); 
        list.add(root.val);
        root = root.right;
      }
      return list;
    }
}

Question 7

In Order Successor of BST

Answer 7

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
      Treenode succ = null;
      while (root != null){
        if (p.val < root.val){
          succc = root;
          root = root.left
        }
        else root = root.right;
      }
      return succ;
    }
}

Recursive
public TreeNode successor(TreeNode root, TreeNode p) {
if (root == null)
return null;

  if (root.val <= p.val) {
    return successor(root.right, p);
  } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
  }
}

Question 8

In Order Predecessor of BST

Answer 8

public TreeNode predecessor(TreeNode root, TreeNode p) {
if (root == null)
return null;

  if (root.val >= p.val) {
    return predecessor(root.left, p);
  } else {
    TreeNode right = predecessor(root.right, p);
    return (right != null) ? right : root;
  }
}

Question 9

Binary Tree Paths

Answer 9

class Solution{
  public List binaryTreePaths(TreeNode root) {
      List result = new ArrayList<>();
      if (root == null) return result;
      helper(root, result, "");
      return result;
  }

public void helper(TreeNode root, List result, String s){
if (root.left ==null && root.right == null){
result.add(s+String.valueOf(root.val));
}
String temp = s+ String.valueOf(root.val) + “->”;
if(root.left != null) helper(root.left, result, temp);
if(root.right != null) helper(root.right, result, temp);
}
}

Question 10

BST Iterator

Answer 10

class BSTIterator {
    Stack stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }

    private void pushAll(TreeNode node){
        while(node != null){
          stack.push(node);
          node = node.left;
        }
    }
    public int next() {
        TreeNode node = stack.pop();
        pushAll(node.right);
        return node.val;
    }

public boolean hasNext() {
    return !stack.isEmpty();
} }

Question 11

Serialize and Deserialize Binary Tree

Answer 11

public class Codec {

    public String serialize(TreeNode root) {
    if (root == null) {
        return "null";
    }
    Queue queue = new LinkedList<>();
    queue.add(root);
    StringBuilder result = new StringBuilder();
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode current = queue.poll();
            if (current == null) {
                result.append("null,");
                continue;
            }
            result.append(current.val).append(",");
            queue.offer(current.left);
            queue.offer(current.right);
        }
    }
    System.out.println(result);
    return result.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] nodes = data.split(",");
    int index = 0;
    if (nodes[index].equals("null")) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(nodes[index++]));
    Queue queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode current = queue.poll();
            if (!nodes[index].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(current.left);
            }
            index++;
            if (!nodes[index].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(current.right);
            }            
            index++;                
        }
    }
    return root;
}
}