Tree Definition

Algorithms
tree
Catalogue
  1. 1. Definition of Tree
  2. 2. Application
    1. 2.1. 388. Longest Absolute File Path
  3. 3. Terms
    1. 3.1. 919. Complete Binary Tree Inserter
      1. 3.1.1. Solution1. Array
      2. 3.1.2. Solution2. Deque
    2. 3.2. 222. Count Complete Tree Nodes
      1. 3.2.1. Follow Up

Definition of Tree

  • at most two children node
1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Application

  • Social networks analysis
  • Information indexing
  • Information compression

388. Longest Absolute File Path

  • use Stack to simulate the traversal of file system
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lengthLongestPath(self, input):
        def countT(s):
            cnt = 0
            for ch in s:
                if ch == '\t':
                    cnt += 1
                else:
                    return cnt
            return cnt

        dirs = input.split('\n')
        res = 0
        stack = []
        for i in range(len(dirs)):
            path = dirs[i]
            n = countT(path)
            while n < len(stack):
                stack.pop()
            stack.append(path[n:])
            if '.' in stack[-1]:
                res = max(res, len('/'.join(stack)))
        return res

Terms

  • Balanced Binary Tree
    Balanced Binary Tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less
  • Complete Binary Tree
    Complete Binary Tree is a banary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • Binary Search Tree
    Binary Search Tree is for every sigle node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

919. Complete Binary Tree Inserter

Solution1. Array

  • For Complete Binary Search Tree, we can use an array to save all the node index! Then we can find its parent using the index relation!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class CBTInserter:
    # Space : O(n) n is the number of the nodes
    def __init__(self, root):
        self.nodes = []
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            self.nodes.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    # Time : O(1)            
    def insert(self, v):
        n = len(self.nodes)
        parent = self.nodes[(n - 1) // 2]
        node = TreeNode(v)
        self.nodes.append(node)
        if n % 2 == 1:
            parent.left = node
        else:
            parent.right = node
        return parent.val


    def get_root(self):
        return self.nodes[0]

Solution2. Deque

  • Have the Same time and space complexity, but actually use half spaces than sol1!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class CBTInserter:

        def __init__(self, root):
            self.root = root
            self.deque = collections.deque()
            queue = collections.deque([root])
            while queue:
                node = queue.popleft()
                if not node.left or not node.right:
                    self.deque.append(node)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        def insert(self, v):
            node = TreeNode(v)
            parent = self.deque[0]
            if not parent.left:
                parent.left = node
            else:
                parent.right = node
                self.deque.popleft()
            self.deque.append(node)
            return parent.val

        def get_root(self):
            return self.root

222. Count Complete Tree Nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def countNodes(self, root):
        if not root:
            return 0
        left = self.getDepth(root.left)
        right = self.getDepth(root.right)
        if left == right:
            return (2**left) + self.countNodes(root.right)
        else:
            return (2**right) + self.countNodes(root.left)


    def getDepth(self, root):
        if not root:
            return 0
        cnt = 0
        cur = root
        while cur:
            cur = cur.left
            cnt += 1
        return cnt

Follow Up

  • Given the key n, binary tree key is [1, 2, 3, 4 …], how to check if the node with key n in the complete binary tree ?
    Time : O(log n)
  • Can you count the number of nodes in complete binary tree, based on previous question?
    Binary Search + Previous Question. Time ($(logn)^2$)
Share