Coding Tricks

Posts

Showing posts from February, 2021

A maths puzzle in Javascript

I have written an app called Hundred. The app has a grid of 3 by 3. Some numbers in the grid are given. You have to fill the rest of the numbers with the condition that sum of each row and sum of each column is 100. I have written the same using HTML and java script now. Here is the source code of the same. HTML <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1"> <style> .grid-container { width:auto; display: grid; grid-row-gap:2px; grid-column-gap:2px; grid-template-columns: 80px 80px 80px ; padding: 10px; } .grid-item { background-color: rgba(255, 255, 255, 0.8); border: 1px solid rgba(0, 0, 0, 0.8); padding: 20px; font-size: 22px; text-align: center; } </style> <script type="text/javascript" src="shataka.js"></script> </head> <body> <h1>Shataka - A <i>numbe

Count the number of leaf nodes

Qn: Write a function to count the number of leaf nodes in a binary search tree. Solution: count = leaf nodes in left subtree + leaf nodes in right subtree If a node is having left link as NULL and right link as NULL, then it is a leaf node. So if this condition is true, the call should return 1. If the node is NULL, the call should return 0. if node is NULL return 0 if node->left==NULL and node->right==NULL return 1 else return count(node->left)+count(node->right)

Count the number of nodes of a binary tree

Question: How do you count the nodes of a binary tree? Solution : Like almost all functions in a binary tree, this algorithm also needs a recursive function. The no. of nodes of a binary tree = 0 if the node is NULL = 1 + no. of nodes in left sub-tree+ no.of nodes in right sub-tree. Calculate recursively for all sub-trees. Here is C++ code for the same. int bintree::count() { return count_leaf_nodes(root); } int bintree::count_nodes(node * nd) { if(nd==NULL) return 0; if(nd->left ==NULL && nd->right==NULL) return 1; return 1+count_nodes(nd->left)+count_nodes(nd->right); }

Deleting a node from binary tree

Write a program to delete a node from binary search tree. Solution : The problem with binary tree operations is that it is nonlinear. When we delete a node from linked list, we link the previous node to the next node so that the list is not broken. But that is not simple in binary tree. Because the node has two next nodes - left child node and right child node. Which do we link to previous node - or parent node? If we link say left child node to the parent of node to be deleted, what do we do with other branch? When a node is to be deleted from a binary search tree, there are 3 possible cases. the node is leaf the node has only one child/subtree the node has both children/subtrees The following recursive algorithm takes care of all three cases nd = root find the node to be deleted if nd->val > delvalue recursively call delete on nd->left and set result to nd->left if nd->val < delvalue recursive, call delete on nd->right and set result to nd->right node is fou