際際滷

際際滷Share a Scribd company logo

Treesandgraphs

Download as PPTX, PDF
Spencer Moran
Spencer Moran

This document discusses different types of trees and graphs. It defines properties of trees including that trees are connected graphs with n-1 edges and no cycles. It describes binary search trees where all descendants to the left of a node are smaller and all to the right are greater. The document also covers heaps, tree traversals, common tree algorithms and their strategies, and briefly mentions graphs.

1 of 16
Download to read offline
Trees and Graphs Spencer Moran 12/3/13
Properties of a Tree Tree is a graph where: n-1 edges Connected No cycles If two of the above are true, then all 3 are true. Tree questions are usually asked to test your understanding of recursion.
Binary Search Trees Binary tree is one where each node as at most 2 children. Binary Search tree is a binary tree where all the descendants to the left of a node are smaller than it and all the descendants to the right are greater than it. Most interview questions focus on binary or binary search trees.
Binary Search Tree Complexity Lookup: O(log n) Insertion: O(log n) Deletion: O(log n) Smallest/Largest element: O(n) Traversal: O(n) Print in sorted order: O(n)
Heaps (Usually) binary tree where each nodes children are smaller (or larger in a Min-heap) than it. Allows for constant time extraction of the largest element in the tree. Lookup becomes O(n) Used if extracting the smallest or largest node is paramount
Searching BFS Queue Searches minimum depths first, always searches lowest depth last High memory requirement Shortest path DFS Stack Explores full depth, doesnt search any particular depth last Low memory requirement
Traversals Pre-order: Explore node, then left children, then right In-order: Explore left children, then node, then right Post-order: Explore left children, then right, then node Implemented using simple recursion
Preorder Traversal
Sample Question Find the height of a binary tree.
Strategy Use recursion Think of each child as its own separate subtree with that node as the root Return 1 + the max of left subtrees height and right subtrees height
Treesandgraphs
Sample Question Given the value of two nodes in a BST, find the lowest common ancestor. You may assume both values exist in the tree.
Strategy Uses the left/right descendant property of a BST to traverse through the nodes. Starting at the root, traverse through the tree. If both values are greater than the current node, go right. If both are smaller than the current, go left. LCA will be the first node you encounter that is between the two nodes you are given.
Treesandgraphs
Other Common Tree Questions Binary tree to heap Is Binary tree a BST? Balance an unbalanced BST (left or right rotation) Count # of leaves
Graphs Graph questions are much more complicated and less common. We will cover graphs during the group meeting.

More Related Content

Treesandgraphs

  • 1. Trees and Graphs Spencer Moran 12/3/13
  • 2. Properties of a Tree Tree is a graph where: n-1 edges Connected No cycles If two of the above are true, then all 3 are true. Tree questions are usually asked to test your understanding of recursion.
  • 3. Binary Search Trees Binary tree is one where each node as at most 2 children. Binary Search tree is a binary tree where all the descendants to the left of a node are smaller than it and all the descendants to the right are greater than it. Most interview questions focus on binary or binary search trees.
  • 4. Binary Search Tree Complexity Lookup: O(log n) Insertion: O(log n) Deletion: O(log n) Smallest/Largest element: O(n) Traversal: O(n) Print in sorted order: O(n)
  • 5. Heaps (Usually) binary tree where each nodes children are smaller (or larger in a Min-heap) than it. Allows for constant time extraction of the largest element in the tree. Lookup becomes O(n) Used if extracting the smallest or largest node is paramount
  • 6. Searching BFS Queue Searches minimum depths first, always searches lowest depth last High memory requirement Shortest path DFS Stack Explores full depth, doesnt search any particular depth last Low memory requirement
  • 7. Traversals Pre-order: Explore node, then left children, then right In-order: Explore left children, then node, then right Post-order: Explore left children, then right, then node Implemented using simple recursion
  • 9. Sample Question Find the height of a binary tree.
  • 10. Strategy Use recursion Think of each child as its own separate subtree with that node as the root Return 1 + the max of left subtrees height and right subtrees height
  • 12. Sample Question Given the value of two nodes in a BST, find the lowest common ancestor. You may assume both values exist in the tree.
  • 13. Strategy Uses the left/right descendant property of a BST to traverse through the nodes. Starting at the root, traverse through the tree. If both values are greater than the current node, go right. If both are smaller than the current, go left. LCA will be the first node you encounter that is between the two nodes you are given.
  • 15. Other Common Tree Questions Binary tree to heap Is Binary tree a BST? Balance an unbalanced BST (left or right rotation) Count # of leaves
  • 16. Graphs Graph questions are much more complicated and less common. We will cover graphs during the group meeting.