LCA (Lowest common ancestor) – binary tree (recursive / example)
Lowest or least common ancestor is the earliest possible node where concerned child nodes joined.
Let us take an example tree, we will discuss some examples to clarify the LCA.
Lowest or least common ancestor is the earliest possible node where concerned child nodes joined.
Let us take an example tree, we will discuss some examples to clarify the LCA.
What is level in binary tree?
As per the definition of binary tree is one, where each node has, at most, 2 children. Each node can have left and right child. The root of the tree, is at level 0. Root’s children are at level 1, etc.
As an example, consider the tree:
We have to calculate the sum of all the nodes in a binary tree. To get the sum of all nodes in binary tree, we need to traverse the whole binary tree and while traversing we can start adding the sum of each node.
Let us define the problem statement, before we start our discussion about calculating the height of binary tree. What is height of Binary tree? Conventionally, the longest path from root to deepest leaf node define the height of binary tree.
Binary tree traversal using level order traversal or breadth first search non recursive algorithm in java (example). Visit root to leaf node level wise.
Binary Tree traversal is broadly categorized into following category
1.) Depth First Traversal
Pre Order Traversal
Post Order Traversal
In Order Traversal
2) Breadth First Traversal or Level Order Traversal.
To delete binary tree, we have to delete all the nodes in the tree. We have discussed about deleting the node in binary search tree in separate post. Before we discuss about deleting tree, we will start from very small tree, then we will use this foundation to delete the whole tree. Suppose we have tree of 3 nodes