Menu
What defines an ancestor? More specifically, would E be an ancestor to H? Or is it more simply that F,C,A are ancestors to H? Maybe even G? I would just like to clear up this simple concept.
230
A node that is connected to all lower-level nodes is called an "ancestor". The connected lower-level nodes are "descendants" of the ancestor node.
A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties: The tree has one node called root. The tree originates from this, and hence it does not have any parent.
Recursive Solution The idea is to traverse the tree in a postorder fashion and search for a given node in the tree. For any node, if the given node is found in either its left subtree or its right subtree, then the current node is an ancestor of it.
proper ancestor of n. A proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n. descendent of n. Any node y for which n is an ancestor of y. Every node is an descendent of itself.
E is not an ancestor of H. It's an uncle because it's a sibling of F, which is the parent of H.
F,C,A are ancestors of H. That's true.
G is not relevant to H at all.
Tree structure relationship notation can be found here (according to Wikipedia)
- A node's "parent" is a node one step higher in the hierarchy (i.e. closer to the root node) and lying on the same branch.
- "Sibling" ("brother" or "sister") nodes share the same parent node.
- A node's "uncles" are siblings of that node's parent.
- A node that is connected to all lower-level nodes is called an "ancestor". The connected lower-level nodes are "descendants" of the ancestor node.
102
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
