Boundary Traversal of a Binary Tree

Algorithm Steps

If the tree is empty, return an empty result.
Add the root node's value to the result if it is not a leaf.
Traverse the left boundary (excluding leaves) from the root and add the node values to the result.
Add all leaf nodes from left to right to the result.
Traverse the right boundary (excluding leaves) from the root, store the node values, and then add them in reverse order to the result.

Boundary Traversal of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isLeaf(node):
    return node.left is None and node.right is None

def addLeftBoundary(root, res):
    cur = root.left
    while cur:
        if not isLeaf(cur):
            res.append(cur.val)
        cur = cur.left if cur.left else cur.right

def addLeaves(root, res):
    if root is None:
        return
    if isLeaf(root):
        res.append(root.val)
    else:
        addLeaves(root.left, res)
        addLeaves(root.right, res)

def addRightBoundary(root, res):
    cur = root.right
    tmp = []
    while cur:
        if not isLeaf(cur):
            tmp.append(cur.val)
        cur = cur.right if cur.right else cur.left
    res.extend(tmp[::-1])

def boundaryTraversal(root):
    if not root:
        return []
    res = []
    if not isLeaf(root):
        res.append(root.val)
    addLeftBoundary(root, res)
    addLeaves(root, res)
    addRightBoundary(root, res)
    return res

if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \   \
    #     4   5   6
    #            /
    #           7
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6, TreeNode(7))))
    print(boundaryTraversal(root))