Archive for category Basics
BINARY SEARCH TREE
This is a very special class of trees known as binary search trees. A binary search tree has binary nodes and the following additional property:
Given a node t, each node to the left is “smaller” than t, and each node to the right is “larger.” This definition applies recursively down the left and right subtrees. Figure 1 shows a binary search tree where characters are stored in the nodes.
Figure 1 also shows what happens if you do an inorder traversal of a binary search tree: you’ll get a list of the node contents in sorted order. In fact, that’s probably how the name inorder originated.
You may wonder what we mean by “smaller” and “larger” in our definition of binary search tree. This depends on the type of data being stored at the nodes. If, for instance, the data is integers, then the meaning of smaller and larger is obvious. More typically, though, the node data is some kind of structure, with one of the fields (called the key) used to make comparisons in a binary search tree.
A quick video to have a better (visual) understanding of a Binary Search Tree.
Go through my previous post about What are Trees if you haven’t already read it to completely understand the binary trees.
In general, tree nodes can have any number of children. In a binary tree, the nodes have no more than two children. Figure 1 has examples of binary trees. Figure 2 isn’t a binary tree because several of its nodes have three children. A node in a binary tree isn’t required to have two children. For example, node b in Figure 1 has only one child. Of course, the leaves of a binary tree have no children.
Every tree has a height, which is defined as the maximum number of nodes that must be visited on any path from the root to a leaf. For instance, the tree in Figure 1 has a height of 3. In turn, the depth of a node is the number of nodes along the path from the root to that node. For instance, node c in Figure 1 has a depth of 1. Also go through How to Find the height of a Binary Tree.
A tree is a hierarchical collection of nodes. One of the nodes, known as the root, is at the top of the hierarchy. Each node can have at most one link coming into it. The node where the link originates is called the parent node. The root node has no parent. The links leaving a node (any number of links are allowed) point to child nodes. Trees are recursive structures. Each child node is itself the root of a subtree. At the bottom of the tree are leaf nodes, which have no children.
There is a directionality to the links of a tree. In the strictest definition of a tree, the links point down the tree, but never up. In addition, a tree cannot contain cycles. That is, no path originating from a node can return to that node.
Figure 1 shows a set of nodes that have the properties of trees. Figure 2 shows a set of nodes that do not constitute a tree. That’s because node d has two parents, and two cycles are present (a–b–d and a–c–d).
Trees represent a special case of more general structures known as graphs. In a graph, there are no restrictions on the number of links that can enter or leave a node, and cycles may be present in the graph.
This is very general definition of a tree, however, specific data structures like Binary Tree are mostly used in real applications in computer science. You would like to read What is a Binary Tree and How to find the height of the Binary Tree?