PreOrder Traversal, Binary Tree
Hello all ! I’m slowly walking into data structures & I mean very slowly. Last week I dabbled in Trees, no to be confused with Tries. What’s the difference? A tree is a structure of recursive nodes, most seen in problems are binary tree and balanced tree. A trie is a kind of tree but mainly used for retrieval hence the name trie, but there all other types of tries. Each type of tree has different behavior, structure and use cases. I recently did a very basic preorder traversal of a binary tree on LeetCode.
To get the expect output of [1,2,3]; a preorder traversal first gets the value of the root/node which is 1, then moves to the left of that node if there is one, then moves to the right. In this particular problem the root one has one child on its right which the number 2. When that node is reached, it will left which is now 3 and since there no more children nodes to check, our search is done. This approach is considered a Depth First Traversal, which our search goes as deep as there is valid nodes until there isn’t. In a preorder traversal the traversal goes from N(node or root),L(eft), then finally, R(ight). Post-order traversal is L,R,N and In-order is L,N,R.
