Tree

1. Definition
2. TODO Binary Tree
3. Advanced Trees
- 3.1. Prefix Tree/Trie
- 3.2. Segment Tree

1 Definition

non linear data structure
A tree can be empty with no nodes or a tree is a structure consisting of one node called root and zero or one or more subtrees.
- each node should have only 1 parent
- no unconnected parts in the graph

2 TODO Binary Tree

3 Advanced Trees

3.1 Prefix Tree/Trie

need to know range of allowed characters

Node Class:

class TrieNode:
  def __init__(self):
    self.children = [None] * 26 # assuming lowercase 26 characters
    self.endsHere = False       # for search() vs prefix()

Visualizing:

              EndsHere: False
              | a | b | c | d |
                    |   |
                   /     \
                  /       \
    --------------         ----------------
    |                                     |
EndsHere: True                      EndsHere: True
| a | b | c | d |                   | a | b | c | d |

While searching make sure to use endsHere boolean to judge is the inserted word ends there

Alternate construction from LC answer:

trie={}
for w in words:
  t=trie
  for c in w:
    if c not in t:
      t[c]={}
    t=t[c]
  t['#']='#'         # used to mark end of word

3.2 Segment Tree

Can be helpful in numerous range query problems such as finding minimum, maximum, sum, greatest common divisor, least common denominator in logarithmic time
Each node contains aggregate information (min, max, sum…)

3.2.1 Structure

Example: 2,4,5,7,8,9

Tree view:

              35
              |
    +---------+--------------+
    |                        |
    6                        29
+---+----+          +--------+-------+
|        |          |                |
2        4          12               17
                +---+----+        +--+---+
                |        |        |      |
                5        7        8      9

Can be implemented using a tree or an array
array view:
- child(i) = 2i + 1 and 2i + 2 (0 based index)
35 29 6 12 17 2 4 5 7 8 9

3.2.2 TODO Array View

Building

bottom up approach

Example

input = [2,4,5,7,8,9]
n = len(input)
tree = [0] * (2 * n)

for i in range(n, 2 * n):
  tree[i] = input[i - n]

for p in range(n - 1, -1, -1):
  l = (2 * p)
  r = (2 * p) + 1
  tree[p] = tree[l] + tree[r]

print(tree)

[35, 35, 29, 6, 12, 17, 2, 4, 5, 7, 8, 9]

Updating Tree

When we change the original array at index i, we need to propagate the change up
update leaf, then its parent…up to the root
Example:

35 29 6 12 17 2 4 5 7 8 9

v

9

39 33 6 16 17 2 4 9 7 8 9

Code

def updateTree(i, val):
  pos = n + i
  tree[pos] = val

  while pos > 0:
    r = l = pos
    # children(i) = 2i and 2i + 1
    if pos % 2 == 0:
      r += 1
    else:
      l -= 1

    p = int(l / 2)
    tree[p] = tree[l] + tree[r]
    pos = p # parent is the new element which has changed

updateTree(2, 9)
print(tree)

[74, 39, 33, 6, 16, 17, 2, 4, 9, 7, 8, 9]

Remember: children(i) = 2i and 2i + 1

TODO Range Query (Sum, Min, Max…)

3.2.3 Tree View

Building

similar to building binary search tree from an sorted array

Example: 2,4,5,7,8,9

                                |  35   |
                                | 0 - 5 |
                                    |
               +--------------------+-------------------+
               |                                        |
           |  11   |                                |  24   |
           | 0 - 2 |                                | 3 - 5 |
               |                                        |
         +-----+------------+                 +---------+------------+
         |                  |                 |                      |
     |   6   |          |   5   |         |  15   |               |  9    |
     | 0 - 1 |          | 2 - 2 |         | 3 - 4 |               | 5 - 5 |
         |                                    |
    +----+--------+                    +------+--------+
    |             |                    |               |
|   2   |     |   4   |            |   7   |       |   8   |
| 0 - 0 |     | 1 - 1 |            | 3 - 3 |       | 4 - 4 |

Code

input = [2, 4, 5, 7, 8, 9]

class Node:
  def __init__(self, val, start, end):
    self.val = val
    self.start = start
    self.end = end
    self.left = None
    self.right = None

def createTree(input, l, r):
  if not input or l > r:
    return None

  root = Node(0, l, r)
  if l == r:
    root.val = input[l]
    return root
  else:
    m = (l + r) // 2
    root.left = createTree(input, l, m)
    root.right = createTree(input, m + 1, r)
    root.val = root.left.val + root.right.val
    return root

segtree = createTree(input, 0, len(input) - 1)
print(segtree.val)

Update

find appropriate index, update the val and re-calculate the val while bubbling-up

Code:

def updateTree(tree, i, val):
  if tree.start == tree.end and tree.start == i:
    tree.val = val
    return

  m = (tree.start + tree.end) // 2
  if i <= m:
    updateTree(tree.left, i, val)
    tree.val = tree.left.val + tree.right.val
    return
  else:
    updateTree(tree.right, i, val)
    tree.val = tree.left.val + tree.right.val
    return

updateTree(segtree, 2, 9)
print(segtree.val)

Range Query

answer queries
- if queried range == node range then return val
- if whole queried range < node range then recursively call left; similar for right
- else split range: query left and right subtree

Code

def query(root, i, j):
  if not root:
    return 0

  if root.start == i and root.end == j:
    return root.val

  m = (root.start + root.end) // 2
  if j <= m:
    return query(root.left, i, j)
  elif i > m:
    return query(root.right, i, j)
  else:
    return query(root.left, i, m) + query(root.right, m + 1, j)

print(query(segtree, 0, 5))
print(query(segtree, 2, 5))
print(query(segtree, 4, 5))

39
33
17

Tree

Table of Contents

1 Definition

2 TODO Binary Tree

3 Advanced Trees

3.1 Prefix Tree/Trie

3.2 Segment Tree

3.2.1 Structure

3.2.2 TODO Array View

3.2.3 Tree View