Ways of adding nodes in a normal binary tree

Question

Take the following binary tree as an example. Let's say we wanted to add some node (the value associated isn't important). Where can we add the node?

In the picture below, I know I can add nodes at the end of the tree (like the green one I drew). But can we also add nodes in the middle of a certain edge (like the red ones I drew)?

I know this isn't true for a Binary Search Tree, but what about a normal Binary Tree? Also, if the answer is affirmative, is there another way of adding nodes in a normal Binary Tree?

Thanks for any help in advance! (and I am sorry about my drawing skills)

Answer 1

can we also add nodes in the middle of a certain edge (like the red ones I drew)?

Yes, the edge splits into two edges, where the inserted node will just have one child.

I know this isn't true for a Binary Search Tree, but what about a normal Binary Tree?

It could sometimes work out for a binary search tree too, but it wouldn't be good practice, as it leads more quickly to an unbalanced tree than the normal insertion procedure would lead to.

is there another way of adding nodes in a normal Binary Tree?

You can also make the new node the root of the binary tree, and its only child would be the old root.