Trees Flashcards
1
Q
Basics 1
A
- A graph structure that is rooted. The first node is referred to as the root
- It’s directed to their children and acyclic
- Each node can have only one parent and can’t be disconnected
- The nodes at the bottom are referred to as leaf nodes or leaves
2
Q
Basics 2
A
- The paths between the root and its leaves are called branches
- The height of a tree is the length of the longest branches. It’s measured from the longest leaf
- The depth of a node is its distance from its tree root. It’s measured from the root
- In some problems may need to store the root node or the parent for each node
3
Q
Types 1
A
- Binary tree:
* Whose nodes have up to two child-nodes
* Many of its operations have a logarithmic time complexity, opposite to an imbalanced tree when using the deepest nodes - K-ary tree: a tree whose nodes have up to ‘K’ child-nodes
- Perfect binary tree: a binary tree whose interior nodes have two child nodes and whose leaf nodes have the same depth length
4
Q
Types 2
A
- Complete binary tree:
* A binary tree that’s almost perfect. Its interior nodes have two child nodes, but its leaf nodes don’t necessarily have the same depth
* The nodes in the last level are as far left as possible - Balanced binary tree:
* A binary tree whose left and right subtrees have heights that differ by no more than 1
* It’s such that the logarithmic time complexity of its operations is maintained - Full binary tree: a binary tree whose nodes have either zero child nodes or two child nodes
5
Q
Types 3
A
- Binary search tree (BST):
* Whose nodes satisfy a special BST property
* A node is said to be a valid BST node if and only if: its value is greater than all the values in the node’s left subtree; its value is less than or equal to all the values in the node’s right subtree; and its children nodes are either BST nodes themselves or null - Traversal modes:
* In-order (left, root, right): traverses as if it’s ordering upwardly the tree
* Pre-order (root, left, right): traverses first the root node, then the left side of it, and finally the right side
* Post-order (left, right, root): traverses the left side of the root node, then the right side, and finally the root node
6
Q
Types 4
A
- Binary heaps:
* Typically are complete trees
* They can be Min-Heaps or Max- Heaps
* A type of binary tree whose nodes satisfy a min or max heap property
* On Max-heaps every node has a value greater than or equal to the value of its child nodes. So the root node has the maximum value
* On Min-heaps every node has a value less than or equal to the value of its child nodes. So the root node has the minimum value
7
Q
Types 5
A
- Tries:
* A tree-like data structure that typically stores characters of a string
* Some actual use cases would be: storing predictive text, autocomplete dictionary, and approximate matching algorithms for spell checking and hyphenation software
8
Q
Space-time complexities
A
- Initializing a tree is a linear operation. It’s O(N) ST
- Traversing an entire tree is a linear operation. It’s O(N) T, O(1) S
- In the case of binary balanced trees, many of its operations have a logarithmic time complexity, opposite to an imbalanced tree when using the deepest nodes