Boundary of Binary Tree


  • 0

    Click here to see the full article post


  • 0
    G

    The first algorithm will not work for [1, null, 2, 3, 4] as this algorithm will include 2 element in both left traversal as well as right traversal. Or I am missing something?


  • 0

    No, 2 will be included only in the right boundary.


  • 0
    G

    Pls check out my recursive solution. It does this in one iteration.
    https://discuss.leetcode.com/topic/87069/java-recursive-solution-beats-94


  • 0

    Please explain why the output of this test case:
    [1,2,null,3,4,null,null,5,6,null,null,null,null]
    is [1,2,3,5,6] not [1,2,3,5,6,4]?

    [4] is not on the right boundary?


  • 0

    @tyuan73 root node doesn't have a right child, then according to the definition of right boundary only root node will be considered in right node. Hence 4 should not be there.


  • 0
    D

    Small typo in "The current node is a root node: In this case, the right child will always be a left boundary node. e.g. relationship between A & C in the above figure."
    It should say "The current node is a root node: In this case, the right child will always be a RIGHT boundary node. e.g. relationship between A & C in the above figure."


  • 0
    L

    Just making "Approach #2 Using PreOrder Traversal" a bit simple as below (accepted):

    public class Solution {
        enum Flag {ROOT, LEFT, RIGHT, MIDDLE};
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
            List<Integer> leftBoundary = new ArrayList<>();
            List<Integer> leaves = new ArrayList<>();
            List<Integer> rightBoundary = new ArrayList<>();
            preOrder(root, leftBoundary, leaves, rightBoundary, Flag.ROOT);
    
            leftBoundary.addAll(leaves);
            leftBoundary.addAll(rightBoundary);
            return leftBoundary;
        }
    
        // root -> left -> right
        private void preOrder(TreeNode root, List<Integer> leftBoundary, List<Integer> leaves, List<Integer> rightBoundary, Flag flag) {
            if (root == null) {
                return;
            }
            //Root
            if (flag == Flag.ROOT || flag == Flag.LEFT) {
                leftBoundary.add(root.val);
            } else if (flag == Flag.RIGHT) {
                rightBoundary.add(0, root.val);
            } else if (root.left == null && root.right == null) {
                leaves.add(root.val);
            }
    
            //Left
            if (root.left != null) {
                preOrder(root.left, leftBoundary, leaves, rightBoundary, childFlag(root, flag, true));
            }
    
            //Right
            if (root.right != null) {
                preOrder(root.right, leftBoundary, leaves, rightBoundary, childFlag(root, flag, false));
            }
        }
    
        private Flag childFlag(TreeNode parent, Flag flag, boolean isLeftChild) {
            if (flag == Flag.ROOT) {
                return isLeftChild ? Flag.LEFT : Flag.RIGHT;
            }
    
            //Parent on left boundary, if exist left child, the right child should be a middle node
            if (flag == Flag.LEFT && !isLeftChild && parent.left != null) {
                return Flag.MIDDLE;
            }
    
            //Parent on right boundary, if exist right node, the left child should be a middle node.
            if (flag == Flag.RIGHT && isLeftChild && parent.right != null) {
                return Flag.MIDDLE;
            }
    
            return flag;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.