[Algorithm] Tree Traversal (Array/C++)

Problem Link: https://binarysearch.com/problems/Tree-Traversal

Hello! Today we’ll be looking at a tree traversal problem. This can be solved quite simply once you know how to traverse to the right child, left child, and “parent”. Traversing to the right and left child is trivial but how can we jump to the parent? It can be solved using the hash map. First, we traverse from the root to the leaf nodes and save each node’s parent into the hash map. Then, perform the particular instructions given in the question.

Implementation

Time Complexity: O(n)