Binary Tree Postorder Traversal


Given a binary tree, return the postorder traversal of its nodes' values.


Input: [1,null,2,3]

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?


The below code uses recursion to traverse the binary tree in post order and collect the values at all nodes.

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    if root!=nil{helper(root, &result)}
    return result

func helper(root *TreeNode, result *[]int){
    if root==nil{ return }
    helper(root.Left, result)
    helper(root.Right, result)
    *result = append(*result, root.Val)


The below solution use an explicit stack to traverse the tree in Post Order. The most important part of this problem is to figure out what to do when you are at a node and there exists a right sub tree.

We solve that issue by pushing a node with the node’s value where there exists a right sub tree.

type Stack []*TreeNode		
func (s *Stack) Push(n *TreeNode) {
    *s = append(*s, n)
func (s *Stack) Pop() (n *TreeNode) {
    x := s.Len() - 1
    n = (*s)[x]
    *s = (*s)[:x]
func (s *Stack) Len() int {
    return len(*s)
func (s *Stack) Peek() *TreeNode {
    x := s.Len() - 1
    return (*s)[x]

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    stack := Stack{}
    cur := root
    for cur!=nil || stack.Len()!=0{
        for cur!=nil{
            cur = cur.Left
        node := stack.Pop()
        if node.Right!=nil{
        } else {
            result = append(result, node.Val)
        cur = node.Right
    return result