What is the root node, and how many roots can a tree have?

The root is the topmost node, the only node without a parent. A tree has exactly one root. A collection of several trees is called a forest.

What is the difference between a leaf node and an internal node?

A leaf has no children. An internal node has at least one child. The root is an internal node unless it is the only node in the tree.

What are siblings, ancestors and descendants?

Siblings: nodes with the same parent. Ancestors: all nodes on the path from a node up to the root. Descendants: all nodes in the subtree below a node.

What is the difference between depth and level?

Both count edges from the root, and the root has depth and level 0, so in most texts they mean the same thing. Some books start counting levels at 1, so it is worth confirming the convention in an interview.

What is the degree of a node and the degree of a tree?

The degree of a node is its number of children. The degree of a tree is the largest degree of any node. A binary tree has a degree of at most 2.

Write a Java method to find the depth of a given value.

Java example: // Returns the depth (edges from the root), or -1 if the value is not found static int depth(TreeNode node, int value, int currentDepth) { if (node == null) { return -1; } if (node.val == value) { return currentDepth; } int left = depth(node.left, value, currentDepth + 1); if (left != -1) { return left; } return depth(node.right, value, currentDepth + 1); } // Call: depth(root, value, 0)

Write a Java method that prints all nodes at a given level.

Java example: static void printLevel(TreeNode node, int level) { if (node == null) { return; } if (level == 0) { System.out.print(node.val + " "); return; } printLevel(node.left, level - 1); printLevel(node.right, level - 1); }

Write a Java method that prints all root-to-leaf paths.

Java example: static void printPaths(TreeNode node, String path) { if (node == null) { return; } path = path.isEmpty() ? String.valueOf(node.val) : path + " -> " + node.val; if (node.left == null && node.right == null) { System.out.println(path); return; } printPaths(node.left, path); printPaths(node.right, path); } // Call: printPaths(root, "")

A subtree is any node together with all its descendants. Every child of a node is the root of its own subtree, which is why most tree algorithms are naturally recursive.

Write a Java method that finds the parent of a given value.

The root has no parent, so the method returns null for it. Java example: static TreeNode findParent(TreeNode node, int value) { if (node == null) { return null; } if ((node.left != null && node.left.val == value) || (node.right != null && node.right.val == value)) { return node; } TreeNode left = findParent(node.left, value); return left != null ? left : findParent(node.right, value); }

Tree Terminology in Data Structure

A Tree is a hierarchical data structure that consists of nodes connected by edges. Each node contains a value (data) and may have zero or more child nodes. The topmost node in a tree is called the root node, and the nodes at the bottom that do not have children are called leaf nodes.

Terminologies in Tree Data Structure

Node: In a tree, Node is an object or entity that contains data and reference (address) to its all child nodes.
For example, In the given tree, there are total 6 Nodes (A, B, C, D, E, F).
Edge: In a tree, Edge makes a connection or link between two nodes. In a tree with 'N' nodes will have a maximum of 'N-1' edges.

For example, in the given tree below, the line connecting Nodes A and B is called an edge.
Root Node: The first node or top most node is a called a Root node, it does have a parent node and it will be a only one in a tree.

In the given tree, A is the root node.
Parent Node: A node that is a node's predecessor is called a Parent node in a tree. A parent node contains the referece (address) of its child nodes.

For better understanding, lets see the tree below.
Child Node: The descendant node of any node is called a child node in a tree.

For example, In the given tree, A is the root node, and B and C are child nodes of A; similarly, D and E are child nodes of B, and F is a child node of C.
Sibling: In general as we know that children of the same parent are called siblings. There is a sample meaning in the tree also, two child nodes connected to a same parent node is called as sibling.

For example, In the given tree below:
- Nodes B and C are siblings.
- Nodes D, E and F are siblings.
- Nodes G and H are siblings.
- Nodes I and J are siblings.
Leaf Node: A node that has no child nodes is known as a leaf node. A leaf node is the tree's lowest node. Leaf nodes are also known as exterior nodes.

For example, we can see in the below tree here D, G, I, J, H are the leaf node.
Degree of a Node: The degree of a node means the total number of its children. A node with the highest degree in a tree is referred to as a degree of tree.

For example, In the given tree below, nodes degree are as follow:
- Node A degree is 2. (B and C are children)
- Node B degree is 3. (D, E and F are children)
- Node C degree is 2. (G and H are children)
- Node E degree is 2. (I and J are children)
Nodes D, F, I, J, G, H degree is 0 as they don't have child.

In tree, all the leave nodes degree is 0.
Height of a node: The height of a node is the total number of edges that connect a leaf node to a specific node along the longest path.

In a tree, height of all leaf nodes will be always '0'.

For better understanding, lets see the tree below.
Depth of a node: In a tree, the total number of edges from the root node to a specific node is known as the depth of that node.

In a tree, depth of root node will be always '0'.

For better understanding, lets see the tree below.
Path: In a tree, the path between two nodes is the sequence of nodes and edges that connects them. The total number of nodes in a path defines its length.

For better understanding, lets see the tree below.
Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node.
For example, In the given tree, Nodes A and B are the ancestor nodes of node {E}.
Descendant: A node x is a descendant of another node y if and only if y is an ancestor of x.

For example, node H is descendant of node C as given in the below tree.
Level of a node: Each step from top to bottom is referred to as a level in a tree. Always a root node level is 0, the next child node is at level 1, the grandchild at level 2, and so on.
Internal node: A node that has one or more child nodes is called an internal node; it is also known as Non-Terminal nodes.

A leaf node will never be an internal node in a tree.

For example, In the given tree below, nodes A, B, C, E, G are Internal Nodes and remaining are leaf nodes.
Neighbour of a Node: The parent or child nodes of that node are referred to as neighbors.

For better understanding, lets see the tree below.
Subtree: In a tree, A subtree will be formed on every single parent node by each child node.

For better understanding, lets see the tree below.

Help Us Improve

Tree Terminology in Data Structure

Terminologies in Tree Data Structure

Frequently Asked Questions (FAQ)