Trees

Question 1

Basics 1

Answer 1

• 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

Question 2

Basics 2

Answer 2

• 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

Question 3

Types 1

Answer 3

• 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

Question 4

Types 2

Answer 4

• 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

Question 5

Types 3

Answer 5

• 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

Question 6

Types 4

Answer 6

• 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

Question 7

Types 5

Answer 7

• 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

Question 8

Space-time complexities

Answer 8

• 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