Random Binary Tree Generator using Python

By Ann Roberts On May 27, 2023

A binary tree is a tree data structure where each node has at most two children, known as the left child and the right child. A random binary tree is a binary tree that is generated randomly with a certain number of nodes. Random binary trees are commonly used for testing algorithms and data structures that rely on binary trees.

Before we dive into the steps needed to generate a random binary tree using Python, let’s understand some concepts related to the topic :

Node: A node is an element in a binary tree that has a value and two children, left and right.
Root: The root is the topmost node in a binary tree.
Left child: The left child of a node is the node that is located to the left of the current node.
Right child: The right child of a node is the node that is located to the right of the current node.
Depth-first search: Depth-first search is a traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking.

To generate a random binary tree, we need to follow these steps

Step 1: Import the Random modules

Step 2: Define a Node class that has a value and two children, left and right.

Python3

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

Step 3: Write a recursive function that generates a random binary tree of a given size.

Python3

def generate_random_binary_tree(size):

if size == 0:

return None

Step 4: Choose the number of nodes in the left subtree and the number of nodes in the right subtree randomly.

Python3

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

Step 5: Generate the left and right subtrees recursively with the chosen sizes.

Python3

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

Step 6: Assign the left and right subtrees to the left and right children of the current node

Python3

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

Step 7: Return the root node

Complete code

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

Examples to Generate a Random Binary Tree of size 5

The Node class defines a node in the tree, with a value, left child node, and right child node. The generate_random_binary_tree() function creates a new node with a random value and recursively generates its left and right subtrees with random sizes. The print_tree() function prints the tree in an indented format by recursively traversing the tree in reverse order.

Finally, the code generates a random binary tree of size 5 and prints it out using the print_tree() function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(" " * 4 * level + "->", node.value)

print_tree(node.left, level + 1)

tree = generate_random_binary_tree(5)

print_tree(tree)

Output

     52
  /     \
42      97
       /  \
     90   88
     
 The root node is 52.
 Its left child is 42 and its right child is 97.
 The right child 97 has a right child 88 and a left child 90.
 The left child 42 has no children.

Traverse the Generated Binary Tree using a Depth-First Search

The Node class defines a node in the tree, with a value, left child node, and right child node. The generate_random_binary_tree() function creates a new node with a random value and recursively generates its left and right subtrees with random sizes. The print_tree function prints the tree in an indented format by recursively traversing the tree in reverse order.

The dfs function performs a preorder DFS traversal of the tree by recursively visiting each node in the tree and printing its value. The function first prints the value of the current node, then visits its left subtree recursively, and then visits its right subtree recursively.

Finally, the code generates a random binary tree of size 5, prints it out using the print_tree() function, and performs a DFS traversal of the tree using the dfs function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(" " * 4 * level + "->", node.value)

print_tree(node.left, level + 1)

def dfs(node):

if node is not None:

print(node.value)

dfs(node.left)

dfs(node.right)

tree = generate_random_binary_tree(5)

print_tree(tree)

print("Preorder DFS: ")

dfs(tree)

print("\n")

Output

-> 86
   -> 67
           -> 46
       -> 78
           -> 90
Preorder DFS: 
86
67
78
90
46

Generate a Random Binary Tree of size 10 and find the Maximum value

In the code, The Node class defines a node in the tree, with a value, left child node, and right child node. The generate_random_binary_tree() function creates a new node with a random value and recursively generates its left and right subtrees with random sizes. The print_tree() function prints the tree in an indented format by recursively traversing the tree in reverse order.

The find_max() function recursively finds the maximum value in the tree by checking the current node’s value, the maximum value in its left subtree, and the maximum value in its right subtree. The function returns negative infinity if the node is None.

Finally, the code generates a random binary tree of size 10, prints it out, and finds the maximum value in the tree using the find_max() function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(' ' * 4 * level + '->', node.value)

print_tree(node.left, level + 1)

def find_max(node):

if node is None:

return float('-inf')

else:

left_max = find_max(node.left)

right_max = find_max(node.right)

return max(node.value, left_max, right_max)

tree = generate_random_binary_tree(10)

print("The generated binary tree is:")

print_tree(tree)

max_value = find_max(tree)

print("The maximum value in the tree is:", max_value)

Output

The generated binary tree is:
   -> 26
       -> 84
-> 1
       -> 45
           -> 34
               -> 20
                       -> 64
                   -> 32
   -> 49
       -> 64
The maximum value in the tree is: 84

Last Updated :
24 May, 2023

Like Article

Save Article

Before we dive into the steps needed to generate a random binary tree using Python, let’s understand some concepts related to the topic :

Node: A node is an element in a binary tree that has a value and two children, left and right.
Root: The root is the topmost node in a binary tree.
Left child: The left child of a node is the node that is located to the left of the current node.
Right child: The right child of a node is the node that is located to the right of the current node.
Depth-first search: Depth-first search is a traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking.

To generate a random binary tree, we need to follow these steps

Step 1: Import the Random modules

Step 2: Define a Node class that has a value and two children, left and right.

Python3

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

Step 3: Write a recursive function that generates a random binary tree of a given size.

Python3

def generate_random_binary_tree(size):

if size == 0:

return None

Step 4: Choose the number of nodes in the left subtree and the number of nodes in the right subtree randomly.

Python3

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

Step 5: Generate the left and right subtrees recursively with the chosen sizes.

Python3

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

Step 6: Assign the left and right subtrees to the left and right children of the current node

Python3

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

Step 7: Return the root node

Complete code

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

Examples to Generate a Random Binary Tree of size 5

Finally, the code generates a random binary tree of size 5 and prints it out using the print_tree() function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(" " * 4 * level + "->", node.value)

print_tree(node.left, level + 1)

tree = generate_random_binary_tree(5)

print_tree(tree)

Output

     52
  /     \
42      97
       /  \
     90   88
     
 The root node is 52.
 Its left child is 42 and its right child is 97.
 The right child 97 has a right child 88 and a left child 90.
 The left child 42 has no children.

Traverse the Generated Binary Tree using a Depth-First Search

The Node class defines a node in the tree, with a value, left child node, and right child node. The generate_random_binary_tree() function creates a new node with a random value and recursively generates its left and right subtrees with random sizes. The print_tree function prints the tree in an indented format by recursively traversing the tree in reverse order.

Finally, the code generates a random binary tree of size 5, prints it out using the print_tree() function, and performs a DFS traversal of the tree using the dfs function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(" " * 4 * level + "->", node.value)

print_tree(node.left, level + 1)

def dfs(node):

if node is not None:

print(node.value)

dfs(node.left)

dfs(node.right)

tree = generate_random_binary_tree(5)

print_tree(tree)

print("Preorder DFS: ")

dfs(tree)

print("\n")

Output

-> 86
   -> 67
           -> 46
       -> 78
           -> 90
Preorder DFS: 
86
67
78
90
46

Generate a Random Binary Tree of size 10 and find the Maximum value

Finally, the code generates a random binary tree of size 10, prints it out, and finds the maximum value in the tree using the find_max() function.

Python3

import random

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def generate_random_binary_tree(size):

if size == 0:

return None

left_size = random.randint(0, size-1)

right_size = size - 1 - left_size

left_subtree = generate_random_binary_tree(left_size)

right_subtree = generate_random_binary_tree(right_size)

root = Node(random.randint(0, 100))

root.left = left_subtree

root.right = right_subtree

return root

def print_tree(node, level=0):

if node is not None:

print_tree(node.right, level + 1)

print(' ' * 4 * level + '->', node.value)

print_tree(node.left, level + 1)

def find_max(node):

if node is None:

return float('-inf')

else:

left_max = find_max(node.left)

right_max = find_max(node.right)

return max(node.value, left_max, right_max)

tree = generate_random_binary_tree(10)

print("The generated binary tree is:")

print_tree(tree)

max_value = find_max(tree)

print("The maximum value in the tree is:", max_value)

Output

The generated binary tree is:
   -> 26
       -> 84
-> 1
       -> 45
           -> 34
               -> 20
                       -> 64
                   -> 32
   -> 49
       -> 64
The maximum value in the tree is: 84

Last Updated :
24 May, 2023

Like Article

Save Article

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.