Hierarchical data are ubiquitous. This makes understanding the techniques on how to process them all the more important. The three standard algorithms are pre-order, in-order, and post-order traversals. This post will look at the mentioned techniques and a few others that will group hierarchical data by rows and columns. We will also explore the top, bottom, right, and left views of a tree. PreOrder, InOrder, and PostOrder Traversals Starting with the standard depth-first traversals, we have pre-order, in-order, and post-order as follows. In depth-first traversal, the algorithm is encouraged to go as far into one branch as possible before backtracking. GroupByDepth Next, we have level-order or group-by-depth. If we only care about printing the node values, then the traditional level-order traversal will do the job. To group the nodes by level, any of the standard depth-first traversals can be used in conjunction with a map of level to list of nodes. A level tracker is also used to track the depth as the algorithm proceeds each subtree. GroupByColumn Vertical-order, or group-by-column, follows a similar implementation to level-order except for one key difference. Instead of tracking depth during the recursive calls, we will add one if we go to the right subtree, and subtract one if we go to the left subtree. Top, Bottom, Left, and Right Views Lastly, getting the right side view of a tree can be done by using one of the depth-first traversals and leveraging the level data to either put the value into a map if it is the first time the level is visited or override the value if the level has been visited before. As the depth-first traversal moves from left to right, the value at the level is overridden until the right-most values remain. Getting the left side view can be accomplished by reversing the traversal order. Getting the top or bottom view relies on the vertical level rather than the depth info.

Evaluate an arithmetic expression written in Reverse Polish Notation and Standard Notation. See the following expressions that yields the same result. Standard Notation: 7 + 3 \* 4 - 5 Reverse Polish Notation: 3 4 \* 7 + 5 - Reverse Polish Notation (Postfix) Evaluate an arithmetic expression in Reverse Polish Notation. The idea is to iterate the array from left to right and push numbers as operands into a stack. There should always be at least two operands in the stack whenever an operator is encountered. The operator indicates the type of operation that should be applied to the top two operands. To apply an operation, two operands are removed from the stack, and the result is pushed back into the stack as a new operand for future calculation. After processing the given expression, the operands stack should be reduced to a single number representing the solution. Standard Notation (Infix) Evaluate an arithmetic expression in Standard Notation. One of the challenges in solving this problem is respecting the order of operations, which is multiplication, division, addition, and subtraction. The intuition is to first resolve all multiplication and division on the first pass. The second pass can be processed from left to right. Similar to the approach for Reverse Polish Notation, a stack can be used to store the operands or the products and quotients from the first pass. This way, the stack will only contain operands that need to be summed up at the end. The time complexity for both problems is O(n) because we need to do processing for each element of the array or string. The space complexity for both problem is O(n) in the case where the operands stack contains as operands as the expression.

Given a sorted array, convert it into a binary search tree. The intuition behind this problem is to recognize that the midpoint of the current range is used to construct the current node. The left child node will be constructed with the midpoint of the left half of the current range. Similarly, the right child node will be constructed using the midpoint of the right half of the current range. We can use the divide-and-conquer technique in solving this problem. At each iteration, we instantiate a new node with the value of the midpoint of the current range. This is recursively applied to the left half and the right half to construct the left and right child, respectively. One important thing to keep in mind is that the range will change with each iteration. The time complexity for this problem is O(n) because we need to do processing for each element of the array. The space complexity for this problem is O(log(n)) because the problem yield a balanced tree where the recursive call stack will be as deep as the height of the tree.

Given a binary tree, find the max value of each level of a Binary Tree. The high level approach to solving this problem involves traversing the tree using one of the three common traversal techniques: pre-order, in-order, or post-order. The depth of each node is tracked during traversal, with the root node being the 0th level. Lastly, a map that associates depth with the maximum value encountered at that level is maintained. Starting at the root, the algorithm checks if the depth of the current node exists as a key in the map. If the current depth does not exist as a key in the map, it means that the current level has not been processed yet. In this case, map the current node's value to its depth, indicating that it's the maximum value seen at that level. If the map already contains the current depth as a key, compare the maximum value seen so far for that level with the value of the current node. If the current node's value is greater, update the map's value for that depth to reflect the new maximum. Once the current node has been processed, continue to traverse to the left and right subtrees and repeat the process. The time complexity for this problem is O(n) because all nodes are processed. The space complexity for this problem depends on the shape of the tree. If the tree is relatively balanced, then the space complexity is close to O(log(n)). If the tree is extremely skewed, then the space complexity is closer to O(n).

Given a binary tree, return all root-to-leaf paths of the tree. This problem can be solved by applying depth-first traversal and processing each level in the pre-order manner. A path is represented as a stack of nodes. A new node is pushed to the current path stack at every node. If the current node is a leaf node, then a new instance of the current path stack is added to the collection of paths. If the current node is not a leaf node, proceed to the next level of the tree. One important note to keep in mind is that arrays (conceptually stack) are passed as reference. This means that extra care must be taken to ensure that the current path stack only contains the path up to that level and nothing more. There are a few approaches to doing this. One way is to keep track of the height of the current level being processed and use that height as an index to modify the value of the array. Once a leaf node is reached, add the subarray from 0 to the height to the collections of path. This approach may not work if the stack implementation does not permit access via index. The second technique is to instantiate a new stack at every level to avoid the unintended pass-by-reference problem. This approach may be memory intensive if the binary tree is large. The last approach is to pop the most recent node once the left and right children are processed. The time complexity of this problem is O(n) because all nodes are processed.

Given a binary tree and a target value, determine if there exists a root-to-leaf path that sums up to the given target. This problem can be solved by applying depth-first traversal and processing each level recursively in a pre-order manner. This means that at each level, we want to subtract the node value from the target value of the current level. If the difference is 0, and the current node has no children, then the current path is one of the possible root-to-leaf paths that sum up to the target. Otherwise, continue to the next node and repeat the process. The time complexity for this problem depends on the shape of the tree. If the tree is relatively balanced, then the time complexity is close to O(log(n)). If the tree is extremely skewed, then the time complexity is closer to O(n).

Given a binary tree, print the nodes in pre-order format. Recursive Approach Pre-order traversal is a technique to systematically process all the nodes in a binary tree. The three steps included in a pre-order traversal are process the current node, move to the left child and recursively apply the pre-order process on the left subtree, and the move to the right child where the pre-order process is recursively applied on the right subtree. The time complexity for pre-order traversal is O(n) where n is the number of nodes on the tree. this is because pre-order traversal processes each node with in the binary tree. Iterative Approach The iterative approach will accomplish the same goal. The general idea is to read the top item and push the children nodes onto a stack at every level. This process is repeatedly applied to the stack as long as it is not empty. The time complexity of the iterative approach is also O(n). Since the iterative approach explicitly uses a stack, space complexity would be O(h) where h is the height of the tree.