Practice Tree Data Structure and Binary Search

Review of Binary Search

Practice

• Sqrt(x)

Review on Iterations

Iteration

Let’s generate a list with 10 random values

>>> import random
>>> A = [random.randint(0,10) for _ in range(10)]
[1, 10, 7, 7, 3, 2, 2, 0, 5, 3]

Iterate through values - three different ways

1. Using range

   >>> for i in range(len(A)):
        print(A[i], end=' ')
   

2. Using in

   >>> for num in A:
        print(num, end=' ')
   

3. Using enumerate

   >>> for i, num in enumerate(A):
        print(i, num)
   

3.1. Using enumerate with 1 as a starting index

>>> for i, num in enumerate(A, 1):
        print(i, num)

Reverse Iteration

>>> for i in reversed(range(len(A))):
        print(i, end=' ')

Reverse using step as -1

>>> for i in range(10, -1, -1):
        print(i, end=' ')

Sorting

>>> A = [(1, 2), (7, 5), (2, 4), (3, 6)]
>>> A.sort()

>>> A = [(1, 2), (7, 5), (2, 4), (3, 6)]
>>> B = sorted(A)

Reversed sort

>>> A = [(1, 2), (7, 5), (2, 4), (3, 6)]
>>> A.sort(reverse=True)

>>> A = [(1, 2), (7, 5), (2, 4), (3, 6)]
>>> B = sorted(A, reverse=True)

Custom Sort

[[1, 3], [1, 4], [2, 4], [3, 6], [4, 2], [7, 5]]
>>> A.sort(key=lambda x: x[1])

A = ['aba', 'ABA', 'James', 'john', 'Andrew', 'lewis', 'Sol', 'Ben', 'Soo', 'jason']
A.sort(key=lambda s: s.lower())

Practice Sorting

• 2Sum
• 3Sum

Tree Recursion

Tree practice (Review)

• Create a tree class (IDLE)
• Create a tree

         5
       /   \
      6     10

• Pre-order
• Post-order
• In-order
• Level-order

Height of tree

• Get height of tree

Insert a node to Binary Search Tree

• Binary Search Tree: Insertion

Lowest Common Ancestor

• Binary Search Tree : Lowest Common Ancestor

More tree problems

• 938. Range Num of BST
• 559. Maximum Depth of N-ary Tree - DFS and BFS
• 531. Find Bottom Left Tree Value

Note:

• https://www.hackerrank.com/topics/binary-search
• https://leetcode.com/tag/binary-search/
• https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/
• https://www.interviewbit.com/courses/programming/topics/binary-search/#problems
• https://www.geeksforgeeks.org/tag/binary-search/