## Data Structure Name: Binary Tree - #### Description: - A tree where each node has at most two children - #### Variations: - [[Heap]] - [[Binary Search Tree (BST)]] - #### Diagram: - #### General Use - Usually, if you want to store data in order and need several operations, such as search, insertion or deletion, at the same time, a BST might be a good choice ## Key Considerations - #### Properties: - #### Implementation Details: | | [[Big O - Time Complexity]] | [[Big O - Space Complexity]] | | ------ | --------------------------- | ---------------------------- | | Access | | | | Add | | | | Delete | | | | Search | | | - #### General Tips - #### Special Properties - Pre-order Traversal - Visit root first, then the left subtree and finish with the right subtree - Add nodes as you visit them - In-order Traversal (think of it like reading left to right) - Traverse Left subtree, visit root, traverse right subtree - Post-order Traversal - Traverse left subtree, traverse right subtree, visit root - Used for deletes and for mathematical expressions - Level Order Traversal (a.k.a [[Pattern7 - Tree-breadth First Search (BFS)]]) - Traverse left to right by level ## Specific Use Cases - Solving Binary Tree Problems with [[General Recursion]] - Top Down - Each recursive call, we will visit the node first to come up with some values and pass these values to its children when calling the function recursively - Thus, it is a type of preorder traversal - Bottom Up - Each recursive call, we will first call the function recursively for all the children nodes and then come up with the answer according to the returned values and the value of the current node itself - Thus, it is a type of post-order traversal