Modifying Binary Trees in CSE 123 Spring 2024
Learn about binary tree modification in CSE 123 Spring 2024, covering topics such as tree structure, programming, traversals, and limitations compared to linked lists.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 BEFORE WE START Talk to your neighbors: What are you looking forward to as it gets warmer? LEC 14 CSE 123 CSE 123 Instructors: Nathan Brunelle Arohan Ashar Neha Rohini Rushil Binary Tree Modification TAs: Ido Zachary Sebastian Joshua Sean Hayden Caleb Justin Heon Rashad Srihari Benoit Derek Chris Bhaumik Kuhu Kavya Cynthia Shreya Ashley Ziao Kieran Marcus Crystal Eeshani Questions during Class? Prakshi Packard Cora Dixon Nichole Raise hand or send here Niyati Trien Lawrence Evan Cady sli.do #cse123A
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 Announcements Programming Assignment 2 due tonight at 11:59pm Programming Assignment 3 out tomorrow - due next Friday!!! (5/30) Quiz 2 next Tuesday (5/27) - Practice quiz released yesterday Quiz 1 grades out later today
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 Review: Binary Trees A Binary Tree is either: 1 null Tree Tree Empty tree Node w/ two subtrees This is a recursive definition! A tree is either empty or a node with two more trees!
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 Review: Binary Tree Programming Programs look very similar to Recursive LinkedList! Guaranteed base case: empty tree - Simplest possible input, should immediately know the return Guaranteed public / private pair - Need to know which subtree you re currently processing If modifying, we use x = change(x) - Don t stop early, return updated subtree (IntTreeNode)
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 Review: Binary Tree Traversals 3 different primary traversals - All concerned with when you process your current root Pre-order traversal: - Process root, left subtree, right subtree In-order traversal: - Process left subtree, root, right subtree Post-order traversal: - Process left subtree, right subtree, root Sometimes different traversals yield different results
LEC 14: Modifying Binary Trees CSE 123 Spring 2024 Modifying Binary Trees Like linked lists, cannot modify nodes - Because data field is final (there are good reasons for this) Will need to create and insert new nodes Use x = change(x), usually 3 times - overall root (in public method) - left subtree - right subtree Order might matter! - Does operation on root depend on children?
