Trees and Transversals Flashcards
What is in order transversal
Left → Root → Right
What is Preorder transversal
Root → Left → Right
What is Postorder transversal
Left → Right → Root
Why are AVL trees used
They are self-balancing BSTs, maintaining O(log n) operations
What’s the height of a complete binary tree with 15 nodes?
3 (0-based), since 15 = 2⁴ - 1
What property defines a min-heap?
Every parent is less than or equal to its children.
What’s the minimum number of nodes in an AVL tree of height h
F(h+2) − 1, where F is the Fibonacci sequence
In an AVL tree, what balance factor range is valid
Must be -1, 0, or +1
What is the balance factor of a leaf node in an AVL tree
0 — both left and right heights are -1
What’s the result of deleting the root in a BST and replacing it with a value from the right subtree?
The smallest value from the right subtree replaces the root
Can a min-heap also be a binary search tree?
No — BSTs must satisfy in-order value rules, heaps only structural.
What is Dikstra’s algorihtm
an aglroithm used to find a shorted parth from a source vertex to all other vertex
What condition would dikstra’s algorithm not work
when the graph contains negative weight edges
how are binary search trees organised
all elements in the left subtree of a node are less than the node. While all subtrees right of the node are greater than the node.
what are the benefits of BST
- printing out values in BST in sorted order
- optimising search operations is the reason we have BSTs
when inserting a value into a BST what value should we compare against to decide whether to place left or right
the parent node ie. the middle one
Why can’t you always just delete nodes in BST, and what should u dop instead
could disconnect tree which you can’t do. Thus you should re organise with on of the bottom nodes
if a tree is balanced what time complexity can most operations be performed at
O(logn)
How do you know if a binary search tree is unbalanced
A binary tree is considered height-balanced if the absolute difference in heights of the left and right subtrees is at most 1 for every node in the tree.
what is one of the most important factors about an AVL tree
rebalancing can be achieved
