Boundary of Binary Tree

MEDIUM

A binary tree boundary is the set of nodes (no duplicates) denoting the union of the left boundaryleaves, and right boundary.

The left boundary is the set of nodes on the path from the root to the left-most node. The right boundary is the set of nodes on the path from the root to the right-most node. The left-most node is the leaf node you reach when you always travel to the left subtree if it exists and the right subtree if it doesn’t. The right-most node is defined in the same way except with left and right exchanged. Note that the root may be the left-most and/or right-most node.

Given the root of a binary tree, return the values of its boundary in a counter-clockwise direction starting from the root.

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The left boundary is nodes [1,2,4].
The right boundary is nodes [1,3,6,10].
The leaves are nodes [4,7,8,9,10].
Unioning the sets together gives [1,2,3,4,6,7,8,9,10], which is [1,2,4,7,8,9,10,6,3] in counter-clockwise order.

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        if(!isLeaf(root)){
            result.add(root.val);
        }
        TreeNode p = root.left;
        while( p != null){
            if(!isLeaf(p)){
                result.add(p.val);
            }
            if(p.left != null){
                p = p.left;
            }else{
                p = p.right;
            }
        }
        addLeaves(root, result);
        Stack<Integer> stack = new Stack<>();
        p = root.right;
        while( p != null){
            if(!isLeaf(p)){
                stack.push(p.val);
            }
            if(p.right != null){
                p = p.right;
            }else{
                p = p.left;
            }
        }
        while(!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }
    
    private boolean isLeaf(TreeNode node){
        return node.left == null && node.right == null;
    }
    
    private void addLeaves(TreeNode node, List<Integer> result){
        if(isLeaf(node)){
            result.add(node.val);
        }
        if(node.left != null){
            addLeaves(node.left, result);
        }
        if(node.right != null){
            addLeaves(node.right, result);
        }
    }
}

Complexity Analysis

  • Time complexity : O(n) One complete traversal for leaves and two traversals upto depth of binary tree for left and right boundary.
  • Space complexity : O(n) resres and stack is used.

Categories: Binary Tree

Tagged as: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s