max depth of a binary tree in c – dead nifty, innit
intro
Oi, you lot! New to C and fancy summat a bit clever? We’re gonna sling together a lil program to find the maximum depth of a binary tree—ya know, how far down them branchy things go from top to bottom. It’s dead simple but proper ace—like when I was tryna count how many floors down the pub cellar went (lost it after two, too smashed). Great for getting yer head round recursion and pointers in C without a right faff. Let’s have a butcher’s!
code bit
Here’s the code—nowt posh, just a quick job I chucked together. Shoved it in a box so it don’t look like a total shambles on yer blog. take a gander:
#include
struct Node { // lil branch, innit
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) { // whip up a branch
struct Node* node=(struct Node*)malloc(sizeof(struct Node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
int maxDepth(struct Node* root) { // dig down deep
if(root==NULL) { // nowt here
return 0; // depth’s 0
}
int leftDepth=maxDepth(root->left); // check left
int rightDepth=maxDepth(root->right); // check right
return (leftDepth>rightDepth?leftDepth:rightDepth)+1; // deepest + 1
}
int main() { // nearly did void, ha!
struct Node* root=newNode(1); // top of the tree
root->left=newNode(2); // left kid
root->right=newNode(3); // right kid
root->left->left=newNode(4); // grandkid
root->left->right=newNode(5); // another grandkid
root->right->right=newNode(6); // one more
printf("max depth of tree is %d\n",maxDepth(root)); // chuck it out
free(root->left->left); // tidy up
free(root->left->right);
free(root->right->right);
free(root->left);
free(root->right);
free(root); // forgot ; once, ugh!
return 0;
}
what ya get
Here’s what it chucks out when ya run it. I hard-coded a lil tree—worked bang on, mate!
how it works, kinda
Right, let’s have a natter bout this like we’re slumped at the boozer with a pint—or a bag of pork scratchings, coz I’m Hank Marvin again. I’ll spill it like my tatty old notes from when I was faffing with C. It’s a doddle once ya clock it, swear down!
1. them `#include` bits
This is me nicking my toolkit. `
2. `struct Node` malarky
`struct Node` is my lil branch—`int data` for the number, `struct Node* left` and `struct Node* right` for pointers to the kids. Like a family tree, innit!
3. `newNode` funtion
`newNode(int data)` makes a fresh branch. `malloc(sizeof(struct Node))` nabs memory, slaps `data` in, sets `left` and `right` to `NULL`, and chucks it back. Like growing a new twig!
4. `int main()` funtion
Gotta have a “main” to kick off—it’s like the door to my local. `int` means I’m lobbing a number out at the end (that `0` says “sorted, guv!”), and them curly `{}` lads keep it all snug. Nearly wrote `void main()`—old me was a right numpty!
5. making the tree: `root` and pals
`root=newNode(1)` starts it—top’s 1. `root->left=newNode(2)` and `root->right=newNode(3)` add kids, then `root->left->left=newNode(4)`, `root->left->right=newNode(5)`, and `root->right->right=newNode(6)` chuck in grandkids. Hard-coded a lil tree—1 at top, 2 left, 3 right, 4 and 5 under 2, 6 under 3.
6. `maxDepth` funtion
Here’s the guts! `maxDepth(struct Node* root)` digs down. If `root==NULL`, `return 0`—no depth. Else, `leftDepth=maxDepth(root->left)` and `rightDepth=maxDepth(root->right)` recurse down each side. `(leftDepth>rightDepth?leftDepth:rightDepth)+1` picks the bigger one and adds 1 for the current level—like counting floors down each pub wing!
7. chucking it out: `printf` and `maxDepth`
`printf("max depth of tree is %d\n",maxDepth(root))` chucks out the deepest level—`%d` slots it, `\n` keeps it tidy. Forgot a `;` once—CODE JUST DIED, and I was proper fuming!
8. `free` and `return 0` to scarper
`free(root->left->left)` and pals tidy up—gotta chuck out all the branches! Then `return 0;` is me legging it, like, “Ta-ta, we’re done!” It’s a C thing—means it all went smooth as a greased weasel.
And that’s yer lot! A cracking lil program to find a binary tree’s max depth. Faff with it—chuck in a daft tree, tweak it to say “deepest drop” if ya fancy. First time I ran this, I got 3 and thought “that’s bang on!”—tree’s 1, 2, 4 deep on left, eh! You’re a star already, mate—keep smashing it! 😊
