Print a Binary Tree from Top to Bottom

1. Problem Description

Print every node of a binary tree from top to bottom, with nodes on the same level printed from left to right.

2. Approach

Use a queue for level-order traversal.

3. Implementation

• java

public class 从上往下打印二叉树
{
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root)
    {
        // Check parameters
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
        {
            return res;
        }

        // Use a queue for level-order traversal
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // As long as the queue is not empty
        while (!queue.isEmpty())
        {
            // Remove the front node and put it into res
            TreeNode treeNode = queue.removeFirst();
            res.add(treeNode.val);
            // Add the left and right nodes to the queue
            if (treeNode.left != null)
            {
                queue.add(treeNode.left);
            }
            if (treeNode.right != null)
            {
                queue.add(treeNode.right);
            }

        }
        return res;
    }
}

• go

// Time complexity: O(n), each node of the binary tree is traversed once
// Space complexity: O(n), each node of the binary tree enters the queue once
func PrintFromTopToBottom(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := make([]int, 0)

	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]

		res = append(res, removed.Val)
		if removed.Left != nil {
			queue = append(queue, removed.Left)
		}
		if removed.Right != nil {
			queue = append(queue, removed.Right)
		}
	}

	return res
}

4. References

• Print a Binary Tree from Top to Bottom - NowCoder