DSA recursive Tree - abukhalil-LTUC-ASAC/amman-401d4 GitHub Wiki
A literal tree
Digital tree atleast, this problem has been defined as peak DSA in terms of understanding the possible solutions to tackle it. A quick mention of what it is, is how you'd imagine a network in the shape of a tree.
The tree starts at the root as a single node, then branches off into other nodes using edges
to connect each node with multiple children nodes and ending with nodes that has no children which are called as leaf. The simplest form of trees are of a binary nature, as in each parent has two children at maximum, called left and right child. The single most defining characteristic of the tree is tis height or how many edges connect between the root and the farthest children.
This is the way
Traversal looks daunting, there are two common solutions to how you could move through the whole tree and guess immediately.
- Breadth First Traversal involves staying at x edge far away and check all nodes at that height, meaning a height of 1 has 2 possible nodes, height of two has 4 possible extra nodes and etc.
- Depth First Traversal means trying to reach the end of a node, before backtracking to the parent and checking for any other ends, then going back again to its parent and seeing the other children, one by one until each end node is reached.