# Tournament Tree and their properties

In this article we are going to learn about the **tournament tree, types of tournament tree, application of tournament tree and their properties**.

Submitted by Prerana Jain, on June 29, 2018

## Tournament Tree

**Tournament tree** is a complete binary tree n external nodes and n-1 internal nodes. The external nodes represent the players and internal nodes represent the winner of the match between the two players.

### Properties of Tournament Tree

- It is rooted tree i.e. the links in the tree and directed from parents to children and there is a unique element with no parents.
- The key value of the parent node has less than or equal to that node to general any comparison operators can be used as long as the relative values of parent-child are invariant throughout the tree. The tree is a parent ordering of the keys.
- Trees with a number of nodes not a power of 2 contain holes which is general may be anywhere in the tree.
- Tournament tree is a proper generalization of heaps which restrict a node to at most two children.
- The tournament tree is also called selection tree.
- The root of the tournament tree represents overall winner of the tournament.

### Types of tournament Tree

There are mainly two type of tournament tree,

**Winner tree****Loser tree**

### 1) Winner tree

The complete binary tree in which each node represents the smaller or greater of its two children is called a winner tree. The smallest or greater node in the tree is represented by the root of the tree. The winner of the tournament tree is the smallest or greatest n key in all the sequences. It is easy to see that the winner tree can be computed in **O(logn)** time.

**Example:** Consider some keys 3, 5, 6, 7, 20, 8, 2, 9

We try to make minimum or maximum winner tree

**Winner tree (minimum)**

### 2) Loser Tree

The complete binary tree for n players in which there are n external nodes and n-1 internal nodes then the tree is called loser tree. The loser of the match is stored in internal nodes of the tree. But in this overall winner of the tournament is stored at tree [0]. The loser is an alternative representation that stores the loser of a match at the corresponding node. An advantage of the loser is that to restructure the tree after a winner tree been output, it is sufficient to examine node on the path from the leaf to the root rather than the sibling of nodes on this path.

**Example:** Consider some keys 10, 2, 7, 6, 5, 9, 12, 1

**Step 1)** We will first draw min winner tree for given data.

**Step 2)** Now we will store losers of the match in each internal nodes.

### Application of Tournament Tree

- It is used for finding the smallest and largest element in the array.
- It is used for sorting purpose.
- Tournament tree may also be used in M-way merges.
- Tournament replacement algorithm selection sort is used to gather the initial run for external sorting algorithms.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions