All Courses

# What are the ways to Inserting a node in a complete binary tree with python

##### By Sde221876@gmail.com, a month ago

How can we insert a node in a complete binary tree without using queue DS?

Binary tree
Node
Python
##### Goutamp777

To insert a node in a complete binary tree using Python, we need to follow the following steps:

1. Traverse the binary tree to find the position where the new node should be inserted.
2. Once we have identified the position to insert the new node, we create a new node with the value we want to insert.
3. Then we assign this new node to the appropriate child of the node where we want to insert it.
4. Finally, we update the parent node to maintain the completeness property of the binary tree.

Here is a Python code snippet that inserts a new node with value val into a complete binary tree represented by an array tree:

```def insert_node(tree, val):
# Calculate the index of the last node in the tree
last_index = len(tree) - 1

# Calculate the index of the parent of the new node
parent_index = (last_index - 1) // 2

# Determine whether the new node should be the left or right child of the parent
if last_index % 2 == 0:
child_index = last_index
else:
child_index = last_index - 1

# Insert the new node into the tree
tree.append(val)

# Update the parent node to maintain the completeness property
if tree[parent_index] is None:
tree[parent_index] = val
elif child_index % 4 == 0:
tree[parent_index * 2 + 1] = val
else:
tree[parent_index * 2 + 2] = val

```

In this code, the tree is a list representing the complete binary tree, where each element represents a node in the tree, and None represents a missing node. The function insert_node takes the tree and the value val to insert and updates the tree in place.

#### Live Masterclass on : "How Machine Get Trained in Machine Learning?" Mar 30th (7:00 PM) 516 Registered
More webinars

#### Related Discussions

Running random forest algorithm with one variable

View More