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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly