13 Ways to Traverse a Tree: Recursion vs Iteration

. I will show you 13 different ways to traverse a tree to compare recursive and iterative implementations. This way, we will kill two birds with one stone: . To understand recursion, you must understand recursion recursion and data structures and algorithms “Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” Recursion, iteration and how to traverse a tree are useful skills to have and common in interview questions. . Do not risk failing your next job interview because you didn’t take the time to read one article I assume you have and are familiar with stacks, queues, recursion, and loops. If this seems too advanced for you, check where I have listed some resources to get you started. basic coding skills this article For every problem, I will provide also a link to Leetcode so that you can play around with my solution or write your own in your preferred programming language. My code examples will be in C++. If you are not familiar with the APIs or syntax, that is fine. I am sure you will understand the ideas. That is the goal of this article. What Is a Tree? Trees are data structures that organize data hierarchically. They are defined from a , that contains the that needs to be stored and . recursively root node data pointers to its children There are many types of trees well-suited for specific applications: , for efficient searches on sorted data. Binary search trees to store database indexes. B-trees to implement . Heaps priority queues General trees to implement . filesystems Etc. . There is no point in storing information if you do not know how to access it For simplicity, I will focus on binary trees. You will take the code and generalize to trees with up to N children per node. I will present you with 13 ways to traverse a tree and discuss them in detail. As usual, there will be challenges for you to cement your knowledge. I strongly recommend solving each problem on your own before reading my solution. You are going to learn infinitely more by doing than by reading or watching. 13 Ways To Traverse a Tree Most of the problems in this section will be on binary trees. We will define a node as follows: val; TreeNode *left; TreeNode *right; TreeNode() : val( ), left( ), right( ) {} TreeNode( x) : val(x), left( ), right( ) {} TreeNode( x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} } { struct TreeNode int 0 nullptr nullptr int nullptr nullptr int Using a struct makes the fields public by default, which is enough for our purposes. For the complexity analysis, we will assume that we will traverse a tree of height that contains nodes. H N 1. Pre-order Traversal – Recursive Given the root of a binary tree, return . the preorder traversal of its nodes’ values You can play around with this problem . here Solution The pre-order, in-order, and post-order traversals of a tree are defined by the order in which we visit the root, left, and right children of a tree. The pre in pre-order refers to the root. In a preorder traversal of a tree, we first visit the root node, then the left node, and finally the right node. You can translate this into recursive code very easily. Your function will receive a node, starting with the root of the tree. You need to define: : As long as the node is not null, Base condition : you process it (for instance, print its value), and then call the same function in the left and right children. Recursive relationship For the base condition, you have two alternatives. I have called them A and B in my code. Have a look at the code and try to figure out the pros and cons of each before you look at my comments. : preorderTraversal(TreeNode* root) { (!root) {}; sol; helperA(root, sol); sol; } { (n){ sol.push_back(n->val); helperA(n->left, sol); helperA(n->right, sol); } } { sol.push_back(n->val); (n->left) helperB(n->left, sol); (n->right) helperB(n->right, sol); } }; { class Solution public vector int if return vector int // helperB(root, sol); return void helperA (TreeNode* n, & sol) vector int if void helperB (TreeNode* n, & sol) vector int if if Alternatives: . Every function call will test whether the node it receives is null or not. Then, it will trigger two recursive calls. This option will result in a larger stack. Option A . The function assumes that the node is not null. It will generate a recursive call only if the left/right child is not null. The function will execute more if statements but make less recursive calls. Option B . In an interview setting, discuss both options. It will show that you care about your code and think of the implications of what you write. There is no right or wrong solution here without more context Your priority should be writing readable and maintainable working code. Only and have proof that these lines of code make a big impact on the overall performance. Don’t guess. Remember. focus on this level of detail when you have profiled your code “Premature optimization is the root of all evil.” Complexity This algorithm visits every node once and adds an element to the end of a vector, which is constant work – . Therefore, the time complexity is O(N). amortized Can you try to figure out the space complexity? Try to visualize the algorithm on the tree above. How many nodes will be stored in the stack in the “worst-case”? I am sure you found the correct answer. The maximum number of nodes that you need to store will be equal to the height of the tree, H. Consequently, the space complexity is O(H). In the next problem, I will show you a non-recursive implementation of the same algorithm to traverse a tree. But before that, I have a little challenge for you. Challenge Given an n-ary tree, return the traversal of its nodes’ values. preorder You can code your solution . here To make you think A natural follow-up to this problem is to generalize it to trees with N children. Before opening the link to Leetcode, try to first . Some interesting questions are: model the nodes yourself What data structures are suitable to store ? at most N children If you a node can have, can you still use this data structure? What other options do you have? don’t know the maximum number of children What if you want to make a generic tree that works for ? The answer to this question will depend on your programming language: templates for C++, Generics for Java, etc. different data types For now, focus only on the recursive solution. Even if “it is trivial”, we have seen that you can still ask questions and discuss different alternatives. 2. Pre-order Traversal – Iterative Traverse a tree using pre-order traversal. No recursion allowed. Give it a try . here Solution Now we will see that recursion is not the only way to traverse a tree. We need to mimic everything that happens under the hood when we use recursive functions. We know that: First, we visit the root of the tree – add it to the solution. Then we process the left child, and finally the right child. We will need to create and handle the stack ourselves instead of relying on recursive calls. A stack is a Last-In-First-Out data structure. Therefore we have to . push the items in the reverse order we want to extract them We can turn this description into the following algorithm: The iterative algorithm begins by adding the root of the tree to a stack . s As long as is not empty, we elements from it. We data structure that represents the because we want to process the parent node before its children. s pop add them to the solution We push the children to . . This way, we will pop the left one before the right one, which is exactly the order in which we want to process them. s First the right child and then the left child : preorderTraversal(TreeNode* root) { (!root) {}; sol; s; s.push(root); (!s.empty()){ t = s.top(); s.pop(); sol.push_back(t->val); (t->right) s.push(t->right); (t->left) s.push(t->left); } sol; } }; { class Solution public vector int if return vector int stack while auto if if return Complexity The complexity analysis does not change with respect to the recursive version. We still need to visit the N nodes and do constant work per node. Therefore the time complexity is O(N). Regarding the space complexity, the stack will have to store at most a number of nodes proportional to the height of the tree, O(H). Challenge It is time for you now to generalize this solution to work with a tree of N nodes. You can test your solution . here 3. In-Order Traversal – Recursive Given the root of a binary tree, return . the inorder traversal of its nodes’ values Give it a try . here Solution In-order traversal is a way to traverse a tree where you first visit the left child, then the root and then the right child. In a binary search tree (like the one above), it will visit the nodes in increasing order. The recursive solution is straightforward. The only difference with the pre-order recursive solution is the order in which we visit the root and the children. It is a minor change. Go ahead and implement it yourself. Everything we discussed about the extra if statements applies to this problem, as well as the discussion about stack vs RAM. Here is a solution with the same options A and B as before. : inorderTraversal(TreeNode* root) { (!root) {}; sol; helperA(root, sol); sol; } { (n){ helperA(n->left, sol); sol.push_back(n->val); helperA(n->right, sol); } } { (n->left) helperB(n->left, sol); sol.push_back(n->val); (n->right) helperB(n->right, sol); } }; { class Solution public vector int if return vector int //helperB(root, sol); return void helperA (TreeNode* n, & sol) vector int if void helperB (TreeNode* n, & sol) vector int if if Complexity The complexity analysis is the same as the previous recursive example. We are doing exactly the same, just in a different order. 4. In-Order Traversal – Iterative Traverse a tree using traversal. No recursion allowed. in-order Test your solution . here Solution I know what you are thinking. You are right. We need a stack. Let’s visualize the in-order traversal of the previous tree. We call the helper function on the root. This calls itself on the left child of the root. This calls itself on the left child of the left child of the root. This process of moving to the left child repeats until we get to a node that has no left child. It is only then when we process that we continue by exploring its right child. k k The implicit stack has stored all the nodes between the root and k. Once we are done with k’s right child, the next node to process will be extracted from the implicit stack. We need to mimic this with our stack. Let’s call it . s To kick-off the tree traversal, we add the root of the tree to s. If the root does have a left child or we have finished exploring the root’s left subtree, we process the root and move to its right child. not Otherwise, this is the case where we keep moving left: 1. We add the root to the stack – to process it later 2. We move to the left From this algorithm, it looks like we need a to mark the node we are currently at. If n becomes null, it means we are done exploring a subtree and need to query the stack for the next node to process. If the stack is empty, we have processed all nodes. stack and a pointer n : inorderTraversal(TreeNode* root) { (!root) {}; sol; s; TreeNode* n = root; (n || !s.empty()) { hasToGoRight = !n; (hasToGoRight){ top = s.top(); s.pop(); sol.push_back(top->val); n = top->right; } { s.push(n); n = n->left; } } sol; } }; { class Solution public vector int if return vector int stack while const bool if auto else return Complexity The complexity analysis is exactly the same as before: O(N) time complexity and O(H) space complexity. 5. Post-Order Traversal – Recursive Given the root of a binary tree, return . the postorder traversal of its nodes’ values Check your implementation . here Solution In a post-order traversal, we first visit the left child, then the last child and finally the root of the tree, hence the name -order. This algorithm requires a minimal change with respect to the pre-order and in-order traversals that we have just seen. post : postorderTraversal(TreeNode* root) { (!root) {}; sol; helperA(root, sol); sol; } { (n){ helperA(n->left, sol); helperA(n->right, sol); sol.push_back(n->val); } } { (n->left) helperB(n->left, sol); (n->right) helperB(n->right, sol); sol.push_back(n->val); } }; { class Solution public vector int if return vector int //helperB(root, sol); return void helperA (TreeNode* n, & sol) vector int if void helperB (TreeNode* n, & sol) vector int if if Complexity Same as pre-order’s and in-order’s. Challenge Try to generalize this to work with N nodes. Code your solution . here 6. Post-Order Traversal – Iterative Traverse a binary tree using traversal. No recursion allowed. post-order Try your solution . here Solution If you are thinking that we need a stack again, you are right. I am familiar with relatively complex solutions based on one stack. This solution can be implemented with two stacks or just one stack and one vector. This can be done with a second stack. The space complexity is still O(N). If you remember correctly, for iterative pre-order traversal we added the root to the solution and then pushed the left and right child. I know this comes out of nowhere, but let’s see what happens if we first push the left child and then the right child. : postorderTraversal(TreeNode* root) { (!root) {}; s; s.push(root); sol; (!s.empty()){ top = s.top(); s.pop(); sol.push_back(top->val); (top->left) s.push(top->left); (top->right) s.push(top->right); } ( x : sol) <<x<< ; sol; } }; { class Solution public vector int if return stack vector int while auto if if for auto cout endl return You can verify that we obtain [18, 21, 22, 20, 16], which is the same as reversing the pre-order traversal of this tree: [16, 20, 22, 21, 18]. We only need to add an extra step at the end of the algorithm to reverse the solution – or use two stacks. I don’t have an intuition for this algorithm. I must admit I had to look up this solution on the internet because I did not want to present more complex alternatives. Above all, it is worth noting is that . sometimes it is useful to play with similar problems to try to get a solution to the problem you are trying to solve : postorderTraversal(TreeNode* root) { (!root) {}; s; s.push(root); sol; (!s.empty()){ top = s.top(); s.pop(); sol.push_back(top->val); (top->left) s.push(top->left); (top->right) s.push(top->right); } reverse(sol.begin(), sol.end()); sol; } }; { class Solution public vector int if return stack vector int while auto if if return Complexity The complexity is linear both in time and space: : we are doing constant work per element. Reversing a vector is also a linear-time operation. Time : the space complexity is linear, whether we use one or two stacks.7. Morris Traversal – How to Traverse a Tree Using Constant Space Space 7. Morris Traversal – How to Traverse a Tree Using Constant Space Traverse a tree using pre-order and in-order traversal. Your space complexity must be O(1) – you cannot use recursion or use any data structures to store information about the nodes. Solution You are right. You still need to store some information about the nodes to visit them. This algorithm modifies the nodes to be able to traverse the tree without explicit data structures. At the end of the algorithm, the nodes is back to their original state. Let’s focus on the in-order traversal. Pre-order just needs a minor modification. We will have two pointers: and . We will use to move around the tree and build links from some leaves back to . . . From this, I can draw a tree and rebuild the algorithm every time. current explorer explorer current Current can only move left if we have previously built a link from its predecessor back to current This is the only thing I have “memorized” about Morris This image has all the links that we will need to build. However, we do not need to keep any of them: . as soon as we are done using a bridge, we destroy it The algorithm goes as follows: First, we set to root. current If have a left child, we add to the solution and move to its right child. current does not current Otherwise: 1. We find t’s predecessor, using . 2. If there is already a link between and , we break it, add to the solution and move to right child. 3. Otherwise, we build a link between and and move to its left child. curren explorer explorer current current current’s explorer current current Go back to 2 until becomes null. current Example Let’s run the algorithm step by step on the tree above: Current starts at 7. Using explorer, we find its predecessor, 6, and link it back to current. We move current to 4. Using explorer, we find its predecessor, 4, and link it back to current. We move current to 2. Current has no left child, so our solution becomes: [2]. We move to current’s right, 4.Using explorer, we find its predecessor, 2. Since explorer (2) is already linking to current (4), we break this link and add 4 to our solution: [2, 4] We move current to its right child, 5. Current has no left child, so we add it to our solution [2, 4, 5] and move to its right child We are in the same situation as step 9. Our solution becomes [2, 4, 5, 6] and current is back at 7. Etc. This is my C++ implementation of this algorithm. : inorderTraversal(TreeNode* root) { sol; current = root; (current){ (!current->left) { sol.push_back(current->val); current = current->right; } { TreeNode* explorer = current->left; (explorer->right && explorer->right != current) { explorer = explorer->right; } (explorer->right == current) { explorer->right = ; sol.push_back(current->val); current = current->right; } { explorer->right = current; current = current->left; } } } sol; } }; { class Solution public vector int vector int auto while if else //Find currents predecessor while //Is it linking back to current? if nullptr else return The difference between in-order and pre-order is in the last block, where we check if there is an existing link or not. We just need to move around the line in which we add current to the solution. For pre-order: (explorer->right == current) { explorer->right = ; current = current->right; } { sol.push_back(current->val); explorer->right = current; current = current->left; } //Is it linking back to current? if nullptr else Morris post-order traversal is a bit trickier, so I will leave it out of this section. Complexity The time complexity is an exercise for you. The space complexity is O(1). We are implicitly using more since we are modifying the tree, but technically we do not need extra space to execute this algorithm. Challenge Can you find some potential issues with this algorithm? For example, if multiple threads had to perform this algorithm on the same tree. 8. Level Order Traversal – Iterative Given a binary tree, return the traversal of its nodes’ values. (ie, from left to right, level by level). level order For this tree, the solution looks like: [[15], [10, 21], [5, 20, 23], [6]]. Try to solve it . here Solution This time I will start with the iterative solution because I find it simpler to code. We can solve this problem by applying . The only trick is how to know when to start a new level. We can do this in two ways: BFS After we push all the nodes in a level, we introduce a special type of node that indicates that we need a new level – for example, a nullptr. Before we start processing the queue, we take note of its size s – the elements at that level. We create a new level after we have process elements. s Here I have taken the second approach. : > levelOrder(TreeNode* root) { (!root) {}; > sol; q; q.push(root); (!q.empty()){ size = q.size(); partial; (size--> ){ n = q.front(); partial.push_back({n->val}); q.pop(); (n->left) q.push({n->left}); (n->right) q.push({n->right}); } sol.push_back(partial); } sol; } }; { class Solution public vector vector int if return vector vector int queue while int vector int while 0 auto if if return Complexity We visit N nodes and do constant work per node. In other words, the time complexity of this approach is O(N). The space complexity is the maximum size of the queue. Since we store elements by level, it is a function of the width of the tree. In the case of a (every node has two children except for the leaves) of height H, the maximum number of nodes in a level will occur at the last level (the leaves), being this 2^H. For this type of tree, H = log2(N). full tree In conclusion, the space complexity is O(N) too. Challenge Try to solve . this variant 9. Level-order Traversal – Recursive Given a binary tree, return the traversal of its nodes’ values. (ie, from left to right, level by level). level order For this tree, the solution looks like: [[15], [10, 21], [5, 20, 23], [6]]. Try to solve the problem . here Solution Always keep in mind the three basic ways to traverse a tree: pre-order, in-order and post-order. This problem is a . pre-order tree traversal in disguise The only extra is that you want . This can be easily achieved using a variable to keep track of the current level you are exploring. to put nodes that are at the same depth together Using a hash table, you can store every node you process at the right depth. Since we are exploring the left child first, the relative order of the elements at each level will be preserved. : > levelOrder(TreeNode* root) { (!root) {}; > levels; helper(root, levels); > sol; ( it = levels.begin(); it != levels.end(); ++it){ sol.push_back(it->second); } sol; } { levels[depth].push_back(n->val); (n->left) helper(n->left, levels, depth + ); (n->right) helper(n->right, levels, depth + ); } }; { class Solution public vector vector int if return //Here is where the magic happens map int vector int //Here we create the solution in the expected data structure vector vector int for auto return void helper (TreeNode* n, > &levels, depth = ) map int vector int int 0 if 1 if 1 Complexity We visit N nodes doing constant work per node (adding an element to a hash table has constant amortized time). Therefore, the time complexity is O(N). This implementation stores all the nodes in a hash table. Consequently, the space complexity is O(N). 10. Level-Order Zigzag Traversal Given a binary tree, return the traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). zigzag level order For this tree, the solution looks like [[8], [14, 4], [2, 5,12,19]]. Give it a try . here Solution This problem might seem challenging at first, but you have the tools to solve it. One of the problems above is very similar to this one. I will give you a minute to find it. You are right. This is a level-order traversal. The only extra is that we have to process . We can achieve this easily with two stacks, s1 and s2. some levels from left to right and others from right to left Imagine we have completed a level from left to right. The last element we pushed to the stack s1 will be the rightmost element at that level of the tree. Firstly, we create a new partial solution – the solution for the new level. We pop the stack s1 and add this element to the partial solution. The next level will be explored from right to left. Therefore, we add first the left child and the right child to the other stack s2 .We keep processing elements from s1 until it is empty. In the next iteration, we will process elements from s2 to complete the next level from left to right. When we process nodes from s2, we first add their right child and then the left child – LIFO for the next level. We do this until both stacks are empty. : > zigzagLevelOrder(TreeNode* root) { (!root) {}; > sol; s1; s2; s1.push(root); (!s1.empty() || !s2.empty()){ partial; (!s1.empty()){ top = s1.top(); partial.emplace_back(top->val); s1.pop(); (top->left) s2.push(top->left); (top->right) s2.push(top->right); } (!partial.empty()){ sol.push_back(partial); partial.clear(); } (!s2.empty()){ top = s2.top(); partial.emplace_back(top->val); s2.pop(); (top->right) s1.push(top->right); (top->left) s1.push(top->left); } (!partial.empty()){ sol.push_back(partial); } } sol; } }; { class Solution public vector vector int if return vector vector int stack stack while vector int while auto if if if while auto if if if return Complexity Both the time and space complexity are linear. Can you see why? Challenges Here I have several variants of this problem for you to keep practicing: Zigzag tree traversal II Generalize to N nodes 11. Side View of a Tree Given a binary tree, imagine yourself standing on the side of it, return the values of the nodes you can see ordered from top to bottom. right The solution for this tree is [16, 19, 18, 13]. Looking from the right side, you cannot see the other nodes because the nodes in the solution “block their view”. Try coding it . here Solution This may look like a challenging problem, but you have the tools you need to solve it. You need to print the rightmost node of each level. Some of the previous problems look very similar o this one. You can solve this problem by modifying the level-order traversal and printing only the last node at each level. This is one possible implementation. : rightSideView(TreeNode* root) { (!root) {}; q; q.push(root); sol; (!q.empty()){ size = q.size(); ( i = ; i val); } (top->left) q.push(top->left); (top->right) q.push(top->right); q.pop(); } } sol; } }; { class Solution public vector int if return queue vector int while int for int 1 auto if if if return Complexity The analysis is the same as the level-order traversal’s. Challenges Here are two variants you can try: Solve this problem recursively Print the left side instead of the right side Print the leaves 12. Vertical-order traversal – Recursive Given a binary tree, return the traversal of its nodes’ values. vertical order For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. Return a list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes. The solution for this example is [[4], [6], [12], [21, 14, 23], [20], [24], [25]]. Code your solution . here Solution I bet you are already seeing a solution. Every time you move left or right, you can keep track of your X position. This is easy to implement recursively. Every time you move to the left node, the X position decreases by 1. If you move to the right, the X position increases by 1. Using a hash table, you can store all the nodes at a certain X position to build the solution. : > verticalTraversal(TreeNode* root) { (!root) {}; >> distances; helper(root, , , distances); > sol; ( x : distances){ sort(x.second.begin(), x.second.end(), [] (pair &a, pair &b) { (a.first==b.first) a.second v; ( y : x.second){ v.push_back(y.second); } sol.push_back(v); } sol; } { (!root) ; distances[hd].push_back({c, root->val}); helper(root->left, hd , c+ , distances); helper(root->right, hd+ , c+ , distances); } }; { class Solution public vector vector int if return map int vector int int 0 0 vector vector int for auto //Using a lambda function to ensure nodes appear in the expected order int int int int if return else return vector int for auto return void helper (TreeNode* root, hd, c, >> &distances) int int map int vector int int if return -1 1 1 1 Complexity We visit every node once and do constant work per node. However, at the last step where we need to order the nodes at each level. This brings the complexity up. It is not trivial to calculate this new complexity but it is clearly bounded by O(NLogN). Since we store all nodes in a hash table, the space complexity is O(N). 13. Vertical-order traversal – Iterative Given a binary tree, return the traversal of its nodes’ values. vertical order For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes. The solution for this example is [[4], [6], [12], [21, 14, 23], [20], [24], [25]]. Test your solution . here Solution Based on my explanation for the previous problem and your understanding of BFS, you will be able to write the iterative version of the algorithm that solves the problem. : > verticalTraversal(TreeNode* root) { >> distances; > q; level = ; q.push({root, }); distances[ ].push_back({level, root->val}); (!q.empty()) { size = q.size(); level++; ( i = ; i left) { distances[sd ].push_back({level, node->left->val}); q.push({node->left,sd }); } (node->right) { distances[sd+ ].push_back({level, node->right->val}); q.push({node->right,sd+ }); } } } > sol; ( it : distances) { partial; sort(it.second.begin(), it.second.end()); ( i= ; i < it.second.size(); i++) { partial.push_back(it.second[i].second); } sol.push_back(partial); } sol; } }; { class Solution public vector vector int map int vector int int queue int int 0 0 0 while const int for int 0 auto int if -1 -1 if 1 1 vector vector int for auto vector int for int 0 return Complexity I will leave this as an exercise for you. If you need hints, check the previous problems. Conclusions This was supposed to be an article on how to traverse a tree. It ended up being an excuse to work on recursive and iterative solutions to the same problem. We can extract a few learnings from this: In general, it is not trivial to translate a recursive algorithm into an iterative. However, this is trivial for functions. tail-recursive Recursive solutions can lead to stack overflow. Always consider iterative solutions (limited by RAM size). Some problems have straightforward recursive solutions and complicated iterative implementations. Recursive solutions tend to be slower because of the stack calls. However, your focus should be on having a working code that is maintainable and readable. Only optimize after using a profiler and finding the real bottlenecks As I have said before, it is not about solving a million problems or spending a million hours. . We have also seen that from a seemingly simple problem we have been able to extract a lot. What is important is what you get out of each hour “No problem is too small or too trivial if we can really do something about it.” The aim of this entry is to . We have seen 13 ways to traverse a tree. We have work on recursive and iterative implementations. . As the next logical step, I invite you to read my article on . make you think about each problem You have become smarter by going through this article dynamic programming . Chances are more people will find it useful too. . If you found this article helpful, please share it You can help someone pass their exams, a job interview, or get them unblocked at work PS: I hope you found this useful. If so, like and share this article, visit my blog , and let's connect on . www.yourdevopsguy.com Twitter