Tree and Graph

Created in January 13, 2025

2025   ·   Data-Structure-and-Algorithms

Tree Basic Concepts

Depth vs. Height

  • The depth of the root node is always 0, as there are no edges between the root and itself
  • Depth is calculated by counting the number of edges (or connections) from the root to the target node

  • The depth of a node is equal to the number of its ancestors, excluding the node itself

  • Depth is measured from the root down to a specific node.
  • Height is measured from a specific node up to the furthest leaf node.

While the depth of the tree (maximum depth of any node) is equal to the height of the tree, the depth and height of individual nodes within the tree are not necessarily the same.

Balanced Tree

  • Height-Balanced Trees: A binary tree is considered height-balanced if for every node, the heights of its left and right subtrees differ by at most 1.

P1. Invert Binary Tree

DFS Solution

This is a solution I came up with today:



1
2
3
4
5
6
7
8
9
10
11

 
TreeNode* invertTree(TreeNode* root) {
	if (!root) {
		return root;
	}

	TreeNode* tmp = root->right;
	root->right = invertTree(root->left);
	root->left  = invertTree(tmp);

	return root;
}

This was a solution I came up with last week:



1
2
3
4
5
6
7
8
9
10
11
12
13
14

 
TreeNode* invertTree(TreeNode* root) {
	if (!root || (!root->left && !root->right) ) {
		return root;
	}

	TreeNode* leftSubtree = invertTree(root->left);
	TreeNode* rightSubtree = invertTree(root->right);

	// Invert
	root->left = rightSubtree;
	root->right = leftSubtree;

	return root;
}

BFS Solution



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

 
TreeNode* invertTree(TreeNode* root) {
	if (!root) {
		return root;
	}

	queue<TreeNode*> q;
	q.push(root);

	while (!q.empty()) {
		int qSize = q.size();
		while (qSize--) {
			TreeNode* node = q.front();
			q.pop();

			if (!node) {
				continue;
			}
			// swap
			TreeNode* tmp = node->left;
			node->left = node->right;
			node->right = tmp;

			q.push(node->left);
			q.push(node->right);
		}
	}
	return root;
}

P2. Maximum Depth of Binary Tree

DFS Solution



1
2
3
4
5
6

 
int maxDepth(TreeNode* root) {
	if (!root) {
		return 0;
	}
	return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

BFS Solution

If you try to solve it with BFS, then you should be particularly careful with NULL leaf node:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

 
int maxDepth(TreeNode* root) {
	if (!root) {
		return 0;
	}
	queue<TreeNode*> q;
	q.push(root);
	int depth = 0;

	while (!q.empty()) {
		int qSize = q.size();

		while (qSize--) {
			TreeNode* node = q.front();
			q.pop();

			if (!node) {
				continue;
			}
			q.push(node->left);
			q.push(node->right);
		}
		depth++;
	}
	// This is wrong, because it also takes null nodes into the count
	// It should be depth-1
	return depth;
}
  • The return value depth is wrong, because at the bottom level it also takes null nodes into the count. It should be depth-1.
  • However, this can be misleading. Let’s change the code so that it prevents from inserting null nodes into the queue:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 
int maxDepth(TreeNode* root) {
	if (!root) {
		return 0;
	}
	queue<TreeNode*> q({root});
	int depth = 0;

	while (!q.empty()) {
		int qSize = q.size();

		while (qSize--) {
			TreeNode* node = q.front(); q.pop();

			if (node->left) {
				q.push(node->left);
			}
			if (node->right) {
				q.push(node->right);
			}
		}
		depth++;
	}
	return depth;
}
  • One thing to note: In C++, you can initialize a queue with one value in two ways:


1
2
3
4
5
6

 
# 1st approach
queue<TreeNode*> q;
q.push(root);

# 2nd approach
queue<TreeNode*> q({root});