A | B |

Node | A node is a structured variable (or object) containing at least one field whose type is a pointer type. ( (A) ) |

Root | The top node in a tree. |

Parent | The converse notion of a child aka the Node above the current Node that is looked/ 15 to a 8 and or 10. |

Child | A node directly connected to another node when moving away from the Root. |

Sibling | A group of nodes with the same parent. |

Descendant | A node reachable by repeated proceeding from parent to child. |

Ancestor | A node reachable by repeated proceeding from child to parent. |

Leaf | A node with no children. |

Interior Node | A node of a tree that has one or more child nodes, equivalently, one that is not a lea |

Subtree | The tree which is a child of a node |

Path | A sequence of nodes and edges connecting a node with a descendant. |

Level | The level of a node is defined by 1 + the number of connections between the node and the root. Level = Depth + 1 |

Depth (of a Node) | The depth of a node is the number of edges from the tree's root node to the node. Depth = Level - 1 |

Height (of a Node) | The height of a node is the number of edges on the longest path between that node and a leaf. |

Binary Tree | A binary tree T is a finite set of nodes such that: T is empty, T consists of a root, R, and exactly two distinct binary trees: left subtree TL, and right subtree TR |

Pre-order Tree Traversal | node, left, right |

In-order Tree Traversal | left, node, right |

Post-order Tree Traversal | left, right, node |

Treesort | To sort a vector: Insert elements into BST, Retrieve them using in-order traversal. Worst case with vanilla BST?: O (N2 ), Average case?: O (N lg (N)). STL tree-based structures worst case?: O (N lg (N)) |

Set | OAC Set maintains a collection of unique values called keys. Set A: 1, 2, etc. Set B: Buick, Honda, etc.Unorder Associative version does the same but it is not in order. No duplicates. |

Map | OAC Map relates keys to values. A29-468 -> 8.75. Unordered Associative version doesn't have them ordered. No duplicates |

Multiset | Set maintains a collection of unique values called keys but now with duplicates. Set A: 1, 2, etc. Set B: Buick, Honda, etc. Unordered Associative version does the same but it is not in order. |

Multimap | Map relates keys to values with duplicates. A29-468 -> 8.75. Unordered Associative version doesn't have them ordered. |

Base case for Trees | Tree is empty, don't do anything |

Trees are used to implement | STL Ordered Associative Containers |