Saturday, April 25, 2020

Binary Trees Traversal Recursive vs. Iterative

Binary tree - Computer Science Wiki
Photo reference:

This neat little trick above saved me a lot of pain and is much quicker to get the traversals. Just think preorder = left, inorder = center, postorder = right. Then weave the string from the top left, to the bottom, to the center, and around until you get to the top right. Wherever the string would 'hook' into a line, write down that number as the next one in that type of traversal.

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

Every recursive problem can be done iteratively using a stack. Recursive calls are simply utilizing the call stack that is an inherent part of the programming language. Don't forget to take into account the space the stack/recursive calls take up when doing the O notation for space!

Recursive solution: Time: O(n)
Space: O(log n) on average. O(n) worst case if tree is one giant linked list going in one direction.

Iterative solution using a stack: Time: O(n)
Space: O(n)