# CP114 Lecture Notes - Lecture 27: Infix Notation, Init, Binary Search Algorithm

## Document Summary

The empty tree is the tree with no nodes and no edges. A graph is a collecion of nodes and edges. A tree is a connected graph with no cycles. i. e. there us exactly one path between two nodes. Difn : a binary tree is either the empty tree or a node that has let and right subtrees that are binary trees. This object is called an extended binary tree. Note that in a binary tree each node has either no children , or one let child, or one right child, or a let child and a right child. Put data in the tree and later search for some key in the data. One lavor- we want visit every node, e. g. to put data in alphapeical order. Another lavour- we want to ind one special node. There are four common transversal orders for binary trees: preorder, inorder, postorder, and level order.