Week2 Coding - How are all leaves of a binary search tree printed?

[kymr]

Problem

• How are all leaves of a binary search tree printed?

[kymr]

Basic Template

• I have slightly modified the LeetCode example.

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  class Solution {
  public void printLeafValues(TreeNode root) {
  
  }
  }

[kymr]

Analysis Requirements

• There are a lot of ways to solve this problem. First, I could traverse the tree recursive or iterative way. Generally, recursive way is easy to develop than iterative way. But I usually implement this kind of problems with iterative way. Solving with recursive way could cause lots of call stack. Also, if error occurs, it is harder to debug.
• Are there any limitations like time-limit or memory for this problem? If not, I am going to try brute force first.
• Isn't the order of leaves important in this problem?

[kymr]

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void printLeafValues(TreeNode root) {

        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<Treenode>();
        stack.push(root);

        while (stack.empty() == false) {
            TreeNode current = stack.pop();

            boolean isLeaf = current.left == null && current.right == null;

            if (isLeaf) {
                System.out.println(current.val);    
            }

            if (current.left != null) {
                stack.push(current.left)
            }

            if (current.right != null) {
                stack.push(current.right);
            }
        }
    }
}

[kymr]

Explanation

• For traversing the tree, Stack is normally used.
• Our goal is printing all leaf values of binary tree. First putting the root node to stack for iterating.
• Every popped node from the stack, checking it is a leaf node or not. If the node is leaf, print it's value. Also if the current node's child exist, then push the children node to stack.
• If the stack is empty, it means all nodes are checked.

[kymr]

Question

• What if the order of all leaves is important, how can you fix it?

[kymr]

Solution for Order

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void printLeafValues(TreeNode root) {

        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<Treenode>();
        stack.push(root);

        while (stack.empty() == false) {
            TreeNode current = stack.pop();

            boolean isLeaf = current.left == null && current.right == null;

            if (isLeaf) {
                System.out.println(current.val);    
            }

            if (current.right != null) {
                stack.push(current.right);
            }

            if (current.left != null) {
                stack.push(current.left)
            }
        }
    }
}

[kymr]

Explanation for Order

• Normally, in-order traversal is used for order. But for this problem, pre-order is also fine. Because we don't care about the node that has children. Even in pre-order, all leaves are kept in order.
• We use stack that is first in last out. When we push the children node to stack, we should push the right node first then left. So that, right node will be popped later.

[kymr]

Question

• Can you implement in-order traversal for that problem?

[kymr]

Solution with in-order traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void printLeafValues(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        Set<TreeNode> addedSet = new HashSet<TreeNode>();
        stack.push(root);

        while (stack.empty() == false) {
            TreeNode current = stack.peek();

            boolean isLeftComplete = current.left == null || addedSet.contains(current.left);

            if (isLeftComplete) {
                stack.pop();
                addedSet.add(current);

                if (current.right != null) {
                    stack.push(current.right);
                } else {
            if (current.left == null) {
                System.out.println(current.val);
            }
        {
            } else {
                stack.push(current.left);
            }
        }
    }
}

[kymr]

Explanation for In-order traversal

• While we traverse tree in in-order, check left node first, then parent node, then right node.
• So, the left node exists and not checked, then push it to stack.
• If left node is already traversed or not exists, then the current node should be checked. If the current.right exists, then push it to stack.
• While checking current node, if the current node doesn't have children, then print the node's value.

[kymr]

There is very simple solution for this

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
         ArrayList<Integer> lst = new ArrayList<Integer>();

        if(root == null)
            return lst; 

        Stack<TreeNode> stack = new Stack<TreeNode>();
        //define a pointer to track nodes
        TreeNode p = root;

        while(!stack.empty() || p != null){

            // if it is not null, push to stack
            //and go down the tree to left
            if(p != null){
                stack.push(p);
                p = p.left;

            // if no left child
            // pop stack, process the node
            // then let p point to the right
            }else{
                TreeNode t = stack.pop();
                lst.add(t.val);
                p = t.right;
            }
        }

        return lst;
    }
}