One key application of recursive algorithms is to perform actions on trees, because trees themselves have a recursive definition. Terminology for trees is summarized in the following table:

Term |
Definition |

Root | Node at the top |

RootInfo(tree) |
The information stored at the root node |

Child of node u |
One of the nodes just under node u |

Parent of node u |
The unique node immediately above node u |

Siblings | Nodes with same parent |

Ancestors of node u |
The nodes on the unique path from the root to the node u |

Descendants of node u |
All the nodes below node u |

Leaf | A node with no children |

Height of tree | The maximum level. Some definitions say that a tree with a single node has height 0, others say height 1. It depends on whether ... |

Start Free Trial

No credit card required