Simple Python iterative solution by using a visited flag - O(n) 56ms

  • 22
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # @param {TreeNode} root
        # @return {integer[]}
        def inorderTraversal(self, root):
            result, stack = [], [(root, False)]
            while stack:
                cur, visited = stack.pop()
                if cur:
                    if visited:
                        stack.append((cur.right, False))
                        stack.append((cur, True))
                        stack.append((cur.left, False))
            return result

  • 0

    Great solution. can you extend such methods to pre-order and post-order search?

  • 0

    i like it ~ thank you~

  • 0

    Could you explain why go node.right first and then node.left? since for the recursive code, it's node.left, res.append(node.val), node.right. Why is it the other way around for iterative

  • 0

    @pennlio Simply change (cur.right, cur, cur.left) triplet

    in-order: (cur.right, cur, cur.left)
    pre-order: (cur.right, cur.left, cur)
    post-order: (cur, cur.right, cur.left)

  • 0

    Brilliant answer. Easy to extend to pre-order and post-order cases.
    I wonder why this answer has so few up-votes.

  • 2

    If you think about it, there are more stack operations than other solutions. Each node will be pushed-popped-pushed-popped.

  • 0

    @edcccccch We are using a stack, we want to make sure that left node is processed before right as needed in inorder traversal. (left->parent->right)
    As stack is LIFO, we first add right node and then left.
    Hope this helps!

Log in to reply

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