ECE 241 / Project 3

FunWithTrees

A movie library in lists and binary search trees

October 29, 2026

app1   /   app2   /   app3   /   app4   /   app5

← / →   previous or next step    O   outline    N   teaching notes    F   fullscreen

Based on project3_f22.pdf and the supplied project3-solution code

ECE 241 / Project 3

Five applications, one movie library

app1Sorted listBinary search, shuffle, save
app2BSTInsert and search by ID
app3Tree traversalIn-order output and text layout
app4Keyword resultsExtract a list, rebuild a tree
app5Tree representationFIFO traversal, array, plot

The same records support several representations and traversal orders.

Source: project3_f22.pdf pp. 2–10; app1.py–app5.py

ECE 241 / Project 3

Movie records and tree nodes

10001;2003;Dinosaur Planet
ID
integerYear
integerTitle
string

A Movie stores one record.

A MovieList holds records in a Python list.

class Node:
    def __init__(self, data):
        self.data = data  # a Movie
        self.left = None
        self.right = None
        self.index = 0

A Node wraps a Movie and adds tree links.

Source: project3_f22.pdf pp. 1–2, 4–5; MovieBST.py, class Node

ECE 241 / app1

Ordered input, then shuffled output

INPUT

oMovies.txt

Ascending movie IDs

10001   10002   10003   …
binarySearch()
then
shuffle() + save()
OUTPUT

Movies.txt

Same records in shuffled order

15544   20522   10873   …
Binary search requires the list to remain sorted by ID.
17,770 records IDs 10001 through 27770

Source: project3_f22.pdf pp. 1–3; app1.py; supplied Movies.txt

ECE 241 / app1

Binary search: finding ID 10007

lower = mid = upper =

The candidate interval includes both endpoints. Yellow marks the current midpoint.

Source: MovieList.py, binarySearch; eight-record teaching subset sorted by ID

ECE 241 / app1

Binary search: an empty interval

lower = mid = upper =

The candidate interval includes both endpoints. Yellow marks the current midpoint.

Source: MovieList.py, binarySearch; ID 10009 is absent from this eight-record subset

ECE 241 / app1

The binary-search loop

lower = 0
upper = self.getSize() - 1
while lower <= upper:
    mid = lower + (upper - lower) // 2
    if self.__movies[mid].getID() == id:
        return self.__movies[mid]
    elif self.__movies[mid].getID() < id:
        lower = mid + 1
    else:
        upper = mid - 1
return None

Loop invariant

If the target exists, its index lies between lower and upper.

Each failed comparison removes the midpoint and one half.

O(log n)

No direct ID-to-index shortcut in this assignment.

Source: MovieList.py, binarySearch; project3_f22.pdf p. 3

ECE 241 / app1

Shuffle: one random swap per position

Five-record teaching subset · same loop as MovieList.shuffle()

out = index = Choose from [0, out]

Move out from right to left. Positions to its right are already fixed.

Source: MovieList.py, shuffle; illustrated with five real IDs and seed 7

ECE 241 / app1

app1: expected behavior

Before the shuffle

  • Load the ordered file into a private list.
  • Search 10,000 generated IDs.
  • Print the first 10 lookup results.
  • Measure the search-loop CPU time.

After the searches

  • Shuffle all movie records.
  • Save them as Movies.txt.
  • Use that file as the input to app2.

A saved shuffled list prepares the BST insertion order.

Source: app1.py; project3_f22.pdf pp. 2–3

ECE 241 / app2

The BST ordering rule

Compare movie IDs

Smaller IDs follow left.

Greater or equal IDs follow right in this implementation.

Each node stores a Movie in node.data.

Diagram: first seven records of Short.txt, in their original insertion order.

Source: MovieBST.py, Node and __recInsert; Short.txt first seven records

ECE 241 / app2

BST insertion: comparisons and links

NEW MOVIE ID

Insert at an empty link

Start at the root.

Compare once at each visited node.

Attach the new Node when the selected child is None.

Seven-record Short.txt subset

Source: MovieBST.py, insert and __recInsert; Short.txt

ECE 241 / app2

Recursive insertion in the supplied code

if new.data.getID() < current.data.getID():
    if current.left is None:
        current.left = new
        new.index = current.index * 2 + 1
        self.__N += 1
    else:
        self.__recInsert(current.left, new)
else:
    # Same structure for the right child
    # right index = current.index * 2 + 2

Two cases

Empty child
Attach the new node.

Existing child
Recurse into that subtree.

The full code also updates the maximum index.

Source: MovieBST.py, __recInsert; condensed excerpt

ECE 241 / app2

BST search: finding ID 19547

TARGET ID
19547
COMPARISON PATH

A missing target reaches a None link.

Source: MovieBST.py, search; seven-record Short.txt subset

ECE 241 / app2

Search cost depends on tree height

Shuffled insertion order

Seven records, maximum depth 3

Sorted insertion order

10181
　↘ 13491
　　 ↘ 14647
　　　 ↘ 19547
　　　　 ↘ 22996
　　　　　 ↘ 25389
　　　　　　 ↘ 26244

Seven records, maximum depth 6

Search and insertion take O(h). A plain BST can have h = n − 1.

Source: MovieBST.py, recursive insertion; sorted version of the same seven IDs

ECE 241 / app3

Tree positions use array-style indices

root: i = 0
left: 2i + 1
right: 2i + 2

Indices describe positions, independent of movie IDs.

For node 14647 at index 4, its right child has index 10.

Seven-record Short.txt subset

Source: project3_f22.pdf p. 5; MovieBST.py, __recInsert

ECE 241 / app3

In-order traversal: left, node, right

RECURSIVE CALLS
OUTPUT SO FAR

Visit happens after the left subtree finishes.

Source: MovieBST.py, __recDisplayInOrder; seven-record Short.txt subset

ECE 241 / app3

In-order output and text layout

displayInOrder()

if current is not None:
    visit(current.left)
    print(current.data)
    visit(current.right)

Left, node, right

10181134911464719547229962538926244

show()

if current is not None:
    show(current.right, indent + "      ")
    print(indent + ID + "(" + index + ")")
    show(current.left, indent + "      ")

Right, node, left

The indentation draws a tree rotated by 90°.

Source: MovieBST.py, __recDisplayInOrder and __recShow; condensed snippets

ECE 241 / app3

The sideways tree, line by line

show() OUTPUT: ID(index)
Source: MovieBST.py, show; seven-record Short.txt subset

      
    



      
ECE 241 / app3
app3: all 20 records of Short.txt

      
In-order traversal prints ascending IDs, regardless of insertion order.
10181The Last Shot
11848Samurai Trilogy 3: Duel at Ganryu Island
12439WWE: Summerslam 2005
13491National Geographic: Beyond the Movie: The…
14647American Yakuza
16969Father Ted: Series 1-2
18361Gulliver's Travels
18478Earth
19416Peyton Place
19547Troll / Troll 2: Double Feature
20957Come September
22522Rancho Deluxe
22996Operation Delta Force 2
23245The John Wayne Collection: Vol. 4: Lawless…
24705Tai Chi 2
24827For Love of the Game
25389The Bride with White Hair
25911War and Remembrance: Vol. 1
26244The Late Show
26394Prime Suspect 4
Source: Short.txt; project3_f22.pdf p. 4; app3.py

      
    



      
ECE 241 / app4
A keyword query produces a new database

      
1
Search word
stars
Scan the full ID-based tree.
2
Result list
15 matching records
In-order extraction sorts them by ID.
3
Saved file
Movies_stars.txt
Shuffle the list before saving.
4
New BST
Build from the saved file.
Display in order and show its layout.
The result tree contains the matching movies. Its shape comes from the new insertion order.
Source: app4.py; project3_f22.pdf pp. 5–7; verified full-dataset count

      
    



      
ECE 241 / app4
Title search uses exact word tokens

      
title = current.data.getTitle()
field = title.lower().split(" ")
if word.lower() in field:
    sublist.insert(current)
Input word: STARS
Lowercase word: stars
Title: The Stars of Star Wars
thestarsofstarwars
Matching behavior
Case does not matter.
star and stars are different tokens.
The code splits on a space and keeps punctuation inside a token.
The tree is ordered by ID, so a title query visits every node.
Source: MovieBST.py, __recExtractListInOrder; condensed snippet; actual record 11237

      
    



      
ECE 241 / app4
Keyword extraction: visit, test, append

      
Seven real records selected for a small stars query
CURRENT TITLE TOKENS
RESULT IDS
Every record is visited, including records that do not match.
Source: MovieBST.py, __recExtractListInOrder; selected records from Movies.txt

      
    



      
ECE 241 / app4
The extracted list becomes a new BST

      
Source object flow
MovieBST node
sublist.insert(current)
MovieList entry is a Node
str(node) delegates to str(node.data)
Movie text record
userListDB.save(filename)
New Movie and Node objects
MovieBST(filename)
Why shuffle again?
In-order extraction returns IDs in ascending order.
Inserting that sorted sequence into a plain BST creates a chain.
Shuffling changes the insertion order before reconstruction.
The rebuilt result tree can have a different shape from the source tree.
Source: MovieBST.py, __recExtractListInOrder and Node.__str__; MovieList.py, save; app4.py

      
    



      
ECE 241 / app5
Queue traversal visits one level at a time

      
First in, first out
Enqueue the root.
Dequeue and visit the front node.
Enqueue its left child, then its right child, when they exist.
Repeat until the queue is empty.
Seven-record Short.txt subset
Source: MovieBST.py, displayLevelOrder; Queue.py

      
    



      
ECE 241 / app5
Level order: the FIFO queue in action

      
FRONTREAR
VISITED IDS
Dequeue first. Then enqueue left and right children.
Source: MovieBST.py, displayLevelOrder; Queue.py; seven-record Short.txt subset

      
    



      
ECE 241 / app5
The array keeps empty tree positions

      
A[node.index] = node.data
7 actual nodes
Maximum index = 10
Array length = 11
Missing children leave None slots.
This is different from a compact list of visited nodes.
Source: MovieBST.py, displayLevelOrder; same seven-record teaching tree

      
    



      
ECE 241 / app5
The supplied level-order method

      
mylist = [None] * (self.getMaxIndex() + 1)
myqueue = Queue()
if self.root is not None:
    myqueue.enqueue(self.root)
while not myqueue.isEmpty():
    current = myqueue.dequeue()
    print(current.data)
    mylist[current.index] = current.data
    if current.left is not None:
        myqueue.enqueue(current.left)
    if current.right is not None:
        myqueue.enqueue(current.right)
return mylist
One pass through the nodes
Each node enters the queue once and leaves it once.
The sparse array has length M = maxIndex + 1.
Including array initialization, this implementation uses O(n + M) time.
A sparse tree can have M much larger than n.
Source: MovieBST.py, displayLevelOrder; condensed local-variable names

      
    



      
ECE 241 / app5
Maximum depth and number of levels

      
depth(i) = ⌊log₂(i + 1)⌋
Root index 0 has depth 0.
Index 10 has depth 3.
Maximum depth = 3.
Number of occupied levels = 4.
getMaxLevel() returns the maximum depth.
Source: MovieBST.py, getMaxLevel; project3_f22.pdf pp. 8–9; seven-record subset

      
    



      
ECE 241 / app5
The lion database used by app5

      
Reproducible app4 input
Keyword: lion
Matching movies: 13
In-order results, shuffled with seed 7
Saved file: Movies_lion.txt
49 max index 50 array slots
First two levels
13746
1288026342
Maximum depth: 5
Number of levels: 6
Read the same saved file in app5 to retain the tree shape.
Source: app4.py and app5.py; Movies.txt; verified seed-7 reconstruction

      
    



      
ECE 241 / app5
Plotting occupied positions in a complete tree

      
The lion result occupies 13 positions in a six-level scaffold.
 empty position movie present
Source: MovieBST.py, plotBST; verified lion result indices

      
    



      
ECE 241 / Project 3
Application checkpoints

      
ApplicationResult to checkImportant condition
app1Movie or None from binary searchList sorted by ID
app2Node or None from BST searchCompare IDs at each node
app3Ascending in-order outputLeft, node, right
app4Keyword list and rebuilt BSTScan all titles, match word tokens
app5Level order, sparse list, tree plotFIFO queue and stable indices
Source: app1.py–app5.py; MovieList.py; MovieBST.py

      
    



      
ECE 241 / Project 3
Questions to close the lecture

      
Why does binary search fail after a shuffle?
Its interval decisions depend on the IDs being sorted.
Why does a title query still scan the whole BST?
The tree’s ordering key is the movie ID, not its title.
Why do array positions contain None?
The array preserves parent-child positions, including empty ones.
Source: algorithms in MovieList.py and MovieBST.py